The finite-list conjecture for 5-vertex-critical co-gem-free graphs
The finite-list conjecture for 5-vertex-critical co-gem-free graphs
A graph is -vertex-critical if it has chromatic number and deleting any vertex lowers its chromatic number; a graph is co-gem-free if it has no induced subgraph isomorphic to the complement of the gem. The paper reports a list of 327 such graphs.
Finite-list conjecture. There are only finitely many -vertex-critical co-gem-free graphs, and the list of 327 is complete.
The finiteness of -vertex-critical co-gem-free graphs is stated to remain open for all . The list was generated computationally for graphs of order at most 18, with no examples of order 13 through 18.
Sources & referencesView supporting material
Primary source
Iain Beaton and Ben Cameron, “Vertex-critical graphs in co-gem-free graphs”, arXiv:2408.05027 (2024).
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.