McDiarmid–Reed conjecture for triangle-free induced subgraphs of the triangular lattice

Let GG be a triangle-free induced subgraph of the triangular lattice, and let bb be a positive integer. The graph GG is (a,b)(a,b)-colorable if, when every vertex receives the same list of aa colors, one can choose bb colors at each vertex so that adjacent vertices receive disjoint color sets.

McDiarmid–Reed conjecture. Every triangle-free induced subgraph of the triangular lattice is

(9b4,b)-colorable.\left(\left\lceil\frac{9b}{4}\right\rceil,b\right)\text{-colorable}.

This conjecture concerns multicoloring for radio-frequency assignment on triangular-lattice networks. The source gives no resolution status; the paper proves the related list-coloring bound (5m,2m)(5m,2m) for finite triangle-free induced subgraphs, rather than the stated ordinary-coloring conjecture.

Sources & referencesView supporting material

Primary source

Yves Aubry, Jean-Christophe Godin and Olivier Togni, “Every triangle-free induced subgraph of the triangular lattice is (5m,2m)-choosable”, arXiv:1110.2650 (2011).

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.