# Non-3-colorable planar 6-vertex graph?

There are $112$ non-isomorphic $6$-vertex planar connected graphs, $81$ of which are $3$-colorable.

I'm searching for one example of an ($n\geq 6$-vertex planar connected graph:

a) that does not contain an even-vertex wheel graph: (W4, W6, W8, W10, etc.)

b) whose vertices are not $3$-colorable

I know that there are plenty of examples, but I can't come up with any.

• How do you know there are plenty of examples? – Henning Makholm Jan 21 '17 at 21:45
• related: arxiv.org/pdf/1309.7120.pdf – Jorge Fernández Hidalgo Jan 21 '17 at 21:56
• @HenningMakholm The paper provided here by Malyshev. – krentze Jan 21 '17 at 21:56
• when you say it contains an even-vertex wheel graph do you mean as an induced subgraph or just as a subgraph? – Jorge Fernández Hidalgo Jan 21 '17 at 21:57
• @JorgeFernándezHidalgo I should have clarified: as an induced subgraph. – krentze Jan 21 '17 at 22:07

## 1 Answer

Here's a generated image of all 99 planar connected 6-vertex graphs:

The non-colorable ones have been painted with red vertices. None of them satisfy condition a).

And, there's an image of all 112 (possibly non-planar) connected 6-vertex graphs (note that the enumeration does not match):

Even here, I can't find any graph that satisfies both a) and b).

So, for $n=6$, there's no such example. For $n=7$, I found several, including these beauties:

                       o-----------o
o               / \         / \
/|\             /   \       /   \
/ | \           /     o     o     \
o--o--o         /   .-  \   /  -.   \
|\   /|        /. -      \ /      - .\
| \ / |       o-----------o-----------o
|  o  |
| / \ |
|/   \|
o-----o

• I tried different visualization algorithms to make it easier to spot the wheels. Here are the results. Planar: 1 2 3 All: 1 2 3 – ThomasR Jan 22 '17 at 22:01
• Is brute force the only viable strategy in order to find a wheel (or 4-clique) in a given graph? – krentze Jan 23 '17 at 0:11
• @EmmaKrentz I'm not an expert in graph theory, so I don't know. – ThomasR Jan 23 '17 at 0:18
• thank you so much for your help! – krentze Jan 23 '17 at 0:19