2
$\begingroup$

Let G be a square with one diagonal.

Are there any planar graphs without G as a subgraph that are not 3-colourable?

1 Answers 1

4

This seems to be related to a (still open I think) conjecture by Bordeaux:

Conjecture (Bordeaux): A planar graph without adjacent $3$-cycles or $5$-cycles is $3$-colorable.

This conjecture is in a sense the best possible since there does exist graphs with chromatic number $4$ without adjacent triangles. The following was found by Havel

                    graph

  • 0
    By the way, here is an easy way to see that the graph cannot be three colorable. You can verify that each of two the hexagonal shaped subgraphs cannot have the top vertex colored the same as the bottom vertex. We can then replace each subgraph with a single edge in which the resulting graph is simply $K_4$ which cannot be three colored.2012-11-19