Hadwiger's conjecture for graphs
Statement
Let be a finite graph and let . A minor of is a graph obtainable from by a sequence of vertex deletions, edge deletions, and edge contractions; write for the chromatic number and for the complete graph on vertices. Hadwiger's conjecture. If , then has as a minor. Equivalently, if does not have as a minor, then . This is a central open problem in graph theory, formulated by Hadwiger in 1943; the source presents it as an open conjecture, while the paper studies its analogue for hypergraphs.
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.