Open Problem Garden

Importance: Medium ✭✭

Author(s):	Oporowski, Bogdan
	Zhao, David

Subject:	Graph Theory
	» Topological Graph Theory
	» » Coloring

Keywords:	coloring
	crossing number
	planar graph

Recomm. for undergrads: yes

Posted	by:	mdevos
	on:	October 9th, 2007

Solved by:

R. Erman, F. Havet, B. Lidicky and O. Pangrac, 5-colouring graphs with 4 crossings, in preparation.

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?

In a nifty paper [OZ], Oporowski and Zhao get a little more mileage out of the classic Kempe-chain proof of the 5-color theorem, proving the following result.

Theorem (Oporowski and Zhao) Every graph $G$ with $cr(G) \le 3$ and $\omega(G) \le 5$ is 5-colorable.

In particular, this shows that every graph with crossing number at most 2 is 5-colorable. The graph $K_6$ can be drawn in the plane with three crossings, so it is clear that the assumption $\omega(G) \le 5$ is necessary in the highlighted theorem. However, it is possible that the assumption $cr(G) \le 3$ might be relaxed. The most extreme example known is the graph $H$ obtained from $K_8$ by removing the edges of a 5-cycle. This graph has $\chi(H) = 6$ , $\omega(H) = 5$ and $cr(H) = 6$ , showing that the $cr(G) \le 5$ bound in the question is best possible.

Erman, Havet, Lidicky and Pangrac [EHLP] further improve this to

Theorem (Erman et al.) Every graph $G$ with $cr(G) \le 4$ and $\omega(G) \le 5$ is 5-colorable.

On the other hand, the graph with $cr(G)=5$ , $\omega(G)=5$ and $\chi(G)=6$ (disproving the original conjecture) can be constructed in the following way: take two copies of $K_6-e$ with non-edges $x_1y_1$ and $x_2y_2$ , respectively. Let $x_1u_1v_1$ and $x_2u_2v_2$ be two triangles in these copies, and identify the corresponding vertices in these triangles. Finally, add the edge $y_1y_2$ .