Goedgebeur and Schaudt's conjecture on 4-vertex-critical -free graphs
Goedgebeur and Schaudt's conjecture on 4-vertex-critical -free graphs
Let denote the path on seven vertices and let denote the cycle on three vertices. A graph is 4-vertex-critical if its chromatic number is and deleting any vertex lowers its chromatic number. A graph is -free if it has no induced subgraph isomorphic to or . Goedgebeur–Schaudt's conjecture. There are exactly seven 4-vertex-critical -free graphs. The conjecture refines the known finiteness result for this class, which gives an upper bound on the order of such graphs but does not determine the exact list.
Sources & referencesView supporting material
Primary source
Yidong Zhou, Jorik Jooken, Baoyuan Shan, Jan Goedgebeur and Shenwei Huang, “Three-coloring triangle-free graphs without long forbidden paths”, arXiv:2512.12349 (2025).
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.