The exhaustive classification of planar 4-critical P_7-free graphs
Statement
A graph is planar if it can be embedded in the plane without crossings. A graph is 4-critical if its chromatic number is 4 and deleting any edge lowers its chromatic number. A graph is -free if it has no induced subgraph isomorphic to the path . Exhaustive classification conjecture. The 52 graphs from Table~ are the only planar 4-critical -free graphs.
This conjecture concerns the unresolved general planar -free case. The authors determined all planar 4-critical -free graphs with at most 30 vertices, and the largest graph found in that range has 13 vertices; whether any further graphs exist remains open.
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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.