Let G be a square with one diagonal.
Are there any planar graphs without G as a subgraph that are not 3-colourable?
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