Erdős, Gimbel and Straight's conjecture for graphs with clique number less than five
Erdős, Gimbel and Straight's conjecture for graphs with clique number less than five
Let be a graph, and write for its clique number, for its cochromatic number, and for its chromatic number. Erdős, Gimbel and Straight's conjecture. Every graph with and satisfies
Erdős, Gimbel and Straight found examples showing that the corresponding bound cannot generally be reduced below for graphs with clique number less than five, but their examples all have cochromatic number at most . The conjecture asserts that graphs with cochromatic number greater than obey the sharper bound; it remains open.
Sources & referencesView supporting material
Primary source
Raphael Steiner, “On the difference between the chromatic and cochromatic number”, arXiv:2408.02400 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.