Wegner's conjecture on the 2-distance chromatic number of planar graphs

About 18 years old · traced to

Let GG be a planar graph with maximum degree Δ\Delta, and let χ2(G)\chi_2(G) denote the minimum number of colors in a coloring in which vertices at distance at most 22 receive distinct colors. Wegner's conjecture.

χ2(G)≤7if Δ=3,\chi_2(G)\leq 7 \quad\text{if } \Delta=3, χ2(G)≤Δ+5if 4≤Δ≤7,\chi_2(G)\leq \Delta+5 \quad\text{if } 4\leq\Delta\leq 7,

and

χ2(G)≤⌊3Δ2⌋+1if Δ≥8.\chi_2(G)\leq \left\lfloor\frac{3\Delta}{2}\right\rfloor+1 \quad\text{if } \Delta\geq 8.

The conjecture remains largely open: the source states that the case Δ=3\Delta=3 was proved by Thomassen, while various weaker upper bounds are known for larger maximum degrees.

References

Primary source

Sara Al Hajjar, “List Coloring of the Square of 4-Irregular Graphs”, arXiv:2607.23160 (2026).

Additional references

37 papers in this index state this conjecture (2008–2026). The statement above is taken from the most recent of them; the others are arXiv:2512.24536, arXiv:2512.10175, arXiv:2508.20825, arXiv:2507.00426, arXiv:2410.02336, arXiv:2406.17191, arXiv:2401.11653, arXiv:2311.02914, arXiv:2311.02201, arXiv:2308.01824, arXiv:2308.00390, arXiv:2307.16394, and 24 more.

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.