Goedgebeur and Schaudt's conjecture on 4-vertex-critical {P7,C3}\{P_7,C_3\}-free graphs

Let P7P_7 denote the path on seven vertices and let C3C_3 denote the cycle on three vertices. A graph is 4-vertex-critical if its chromatic number is 44 and deleting any vertex lowers its chromatic number. A graph is {P7,C3}\{P_7,C_3\}-free if it has no induced subgraph isomorphic to P7P_7 or C3C_3. Goedgebeur–Schaudt's conjecture. There are exactly seven 4-vertex-critical {P7,C3}\{P_7,C_3\}-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

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.