The finite-list conjecture for 5-vertex-critical co-gem-free graphs

A graph is 55-vertex-critical if it has chromatic number 55 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 55-vertex-critical co-gem-free graphs, and the list of 327 is complete.

The finiteness of kk-vertex-critical co-gem-free graphs is stated to remain open for all k5k\geq 5. 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

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.