Non-3-colorable planar 6-vertex graph?

230 Views Asked by At

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.

1

There are 1 best solutions below

4
On BEST 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).

all 99 planar connected 6-vertex graphs

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).

all 112 connected 6-vertex graphs

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