Dichotomy conjecture for finite families of vertex-critical H-free graphs
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.
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
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.