Erdős, Gimbel and Straight's conjecture for graphs with clique number less than five

Let GG be a graph, and write ω(G)\omega(G) for its clique number, ζ(G)\zeta(G) for its cochromatic number, and χ(G)\chi(G) for its chromatic number. Erdős, Gimbel and Straight's conjecture. Every graph GG with ω(G)<5\omega(G)<5 and ζ(G)>3\zeta(G)>3 satisfies

χ(G)ζ(G)+2.\chi(G)\le \zeta(G)+2.

Erdős, Gimbel and Straight found examples showing that the corresponding bound cannot generally be reduced below 33 for graphs with clique number less than five, but their examples all have cochromatic number at most 33. The conjecture asserts that graphs with cochromatic number greater than 33 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.