Dichotomy conjecture for finite families of vertex-critical H-free graphs
Let , let be a graph, and let a graph be -vertex-critical if it has chromatic number and deleting any vertex lowers its chromatic number. A graph is -free if it has no induced subgraph isomorphic to .
Dichotomy conjecture. There is a finite number of -vertex-critical -free graphs if and only if is an induced subgraph of for some .
This conjecture would resolve the open problems concerning the finiteness of -vertex-critical graphs avoiding , , 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
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.