Alon–Krivelevich–Sudakov conjecture on coloring graphs with forbidden subgraphs
Statement
Let be a graph. A graph is -free if it contains no copy of ; write for its chromatic number and let be its maximum degree.
Alon–Krivelevich–Sudakov conjecture. For every graph , there is a constant such that, whenever is an -free graph of maximum degree , one has
Alon, Krivelevich, and Sudakov verified the conjecture for a class of graphs including all bipartite graphs, and subsequent work gives sharper bounds for some complete bipartite forbidden graphs. The conjecture is therefore resolved for some , but the general assertion 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.