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
    Thank you very much for your reply, but of what relevance is that graph?2012-11-19
  • 0
    That's a graph without two adjacent triangles which is not $3$-colorable. Doesn't that directly answer your question?2012-11-19
  • 0
    Huh, I could have swore I eyeballed a 3-coloring to it. Is there any chance you could point me to further reading on Bordeaux's conjecture?2012-11-19
  • 0
    I'm not too sure about the literature on the conjecture. The above picture was obtained from the first link after searching for Bordeaux's conjecture on Google. That paper does discuss it a little but it doesn't seem to be a well known conjecture (at least under this name).2012-11-19
  • 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