Hajós' 4-coloring conjecture for graphs without a topological K5K_5

Let GG be a graph, and let TK5TK_5 denote a subdivision of K5K_5. A graph is 4-colorable if its vertices can be colored with four colors so that adjacent vertices receive different colors.

Hajós' conjecture. Every graph containing no TK5TK_5 is 4-colorable.

The conjecture would generalize the Four Color Theorem. The supplied source does not give a resolution for the k=4k=4 case, so the conjecture remains open.

Sources & referencesView supporting material

Primary source

Dawei He, Yan Wang and Xingxing Yu, “The Kelmans-Seymour conjecture IV: a proof”, arXiv:1612.07189 (2016).

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.