Zhao, David

5-coloring graphs with small crossing & clique numbers ★★

For a graph $G$ , we let $cr(G)$ denote the crossing number of $G$ , and we let $\omega(G)$ denote the size of the largest complete subgraph of $G$ .

Question Does every graph $G$ with $cr(G) \le 5$ and $\omega(G) \le 5$ have a 5-coloring?

Posted by mdevos
updated October 9th, 2007