2
$\begingroup$

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.

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

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
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – ThomasR Jan 22 '17 at 22:01
  • $\begingroup$ Is brute force the only viable strategy in order to find a wheel (or 4-clique) in a given graph? $\endgroup$ – krentze Jan 23 '17 at 0:11
  • $\begingroup$ @EmmaKrentz I'm not an expert in graph theory, so I don't know. $\endgroup$ – ThomasR Jan 23 '17 at 0:18
  • $\begingroup$ thank you so much for your help! $\endgroup$ – krentze Jan 23 '17 at 0:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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