Langhede and Thomassen's exponential correspondence-colouring conjecture for planar graphs

Let GG be a planar graph. A correspondence assignment (L,M)(L,M) for GG consists of a list assignment LL and, for each edge, a partial matching between the corresponding vertex-colour pairs; an (L,M)(L,M)-colouring chooses a colour from each list while avoiding matched pairs on every edge. The class of planar graphs has exponentially many 55-correspondence colourings if there exists a constant c>0c>0 such that every planar graph GG and every 55-correspondence assignment (L,M)(L,M) admit at least 2cv(G)2^{c\cdot v(G)} distinct (L,M)(L,M)-colourings.

Langhede and Thomassen's conjecture. Planar graphs have exponentially many 55-correspondence colourings.

This conjecture asks for an exponential strengthening of the known 55-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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.