Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let G be a square with one diagonal.

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

share|cite|improve this question
up vote 4 down vote accepted

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


share|cite|improve this answer
Thank you very much for your reply, but of what relevance is that graph? – P____ Nov 19 '12 at 6:06
That's a graph without two adjacent triangles which is not $3$-colorable. Doesn't that directly answer your question? – EuYu Nov 19 '12 at 6:09
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? – P____ Nov 19 '12 at 6:14
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). – EuYu Nov 19 '12 at 6:16
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. – EuYu Nov 19 '12 at 6:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.