ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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 k≥5k\geq 5. The list was generated computationally for graphs of order at most 18, with no examples of order 13 through 18.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.