Raphael Steiner
Published 2024-08-05Version 1
The cochromatic number $\zeta(G)$ of a graph $G$ is the smallest number of colors in a vertex-coloring of $G$ such that every color class induces an independent set or a clique. In 1988, Erd\H{o}s, Gimbel and Straight conjectured that every $K_5$-free graph $G$ with $\zeta(G)>3$ satisfies $\chi(G)\le \zeta(G)+2$. In this note, we present a counterexample to this conjecture and discuss related results and questions.
On a question of Erdős and Gimbel on the cochromatic number
A solution to a conjecture on the rainbow connection number
On a Conjecture of Andrica and Tomescu
![QR code for arXiv:2408.02400 [math.CO]](http://oss.arxitics.com/images/favicon.svg)