Dichotomy conjecture for finite families of vertex-critical H-free graphs

Let k5k\geq 5, let HH be a graph, and let a graph be kk-vertex-critical if it has chromatic number kk and deleting any vertex lowers its chromatic number. A graph is HH-free if it has no induced subgraph isomorphic to HH.

Dichotomy conjecture. There is a finite number of kk-vertex-critical HH-free graphs if and only if HH is an induced subgraph of P4+sP1P_4+sP_1 for some s0s\geq 0.

This conjecture would resolve the open problems concerning the finiteness of kk-vertex-critical graphs avoiding P3+2P1P_3+2P_1, P4+P1P_4+P_1, and their generalizations to graphs on at least five vertices. The supplied text does not state whether the conjecture has been resolved.

Sources & referencesView supporting material

Primary source

Ben Cameron, Chính T. Hoàng and Joe Sawada, “Dichotomizing k-vertex-critical H-free graphs for H of order four”, arXiv:2007.00057 (2020).

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.