# Can a planar graph without two triangles that share an edge have a chromatic number larger than 3?

Let G be a square with one diagonal.

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

-

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

-
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