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

About 6 years old · traced to

Let k≥5k\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 s≥0s\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.

References

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.