5-coloring graphs with small crossing & clique numbers (Solved)

Importance: Medium ✭✭
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 $.

Bibliography

*[OZ] B. Oporowski and D. Zhao, Coloring graphs with crossings.

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


* indicates original appearance(s) of problem.