Langhede and Thomassen's exponential correspondence-colouring conjecture for planar graphs
Langhede and Thomassen's exponential correspondence-colouring conjecture for planar graphs
Let be a planar graph. A correspondence assignment for consists of a list assignment and, for each edge, a partial matching between the corresponding vertex-colour pairs; an -colouring chooses a colour from each list while avoiding matched pairs on every edge. The class of planar graphs has exponentially many -correspondence colourings if there exists a constant such that every planar graph and every -correspondence assignment admit at least distinct -colourings.
Langhede and Thomassen's conjecture. Planar graphs have exponentially many -correspondence colourings.
This conjecture asks for an exponential strengthening of the known -correspondence-colourability of planar graphs. The source gives no resolution, so the conjecture remains open.
Sources & referencesView supporting material
Primary source
Luke Postle and Evelyne Smith-Roberge, “Exponentially Many Correspondence Colourings of Planar and Locally Planar Graphs”, arXiv:2309.17291 (2023).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.