As the question asks, is it possible for a graph to have a chromatic number larger than three without it having a 4 vertice complete graph as a sub-graph?
Can a graph be non 3-colourable without having k4 as a sub graph?
-
3In general, there's no "easy" characterization of 3-colorability. Determining whether a graph is 3-colorable is NP-complete, so no characterization can be in P (such as checking whether it contains $K_4$, which is $O(n^4)$). – 2012-10-31
4 Answers
Here's a simple counterexample with 6 vertices. Take a 5-cycle $C_5$. Add a new vertex $A$ and connect it by an edge with each vertex of $C_5$. The resulting graph is not 3-colorable. It it were 3-colorable, then $C_5$ would be 2-colorable, which it isn't.
-
0@Douglas S. Stones This is offtopic, but what software did you use to draw the diagram? – 2012-11-02
-
0I pinched it from Wikipedia: [here](http://en.wikipedia.org/wiki/Wheel_graph); listed as "Released into the public domain (by the author)." It would be possible to draw it this way using [tikz](http://www.texample.net/tikz/). – 2012-11-02
-
0question about this. doesn't Dirac's theorem say that if a graph is $4$-colorable then it must contain a subdivision of $K_4$? If this example is correct, wouldn't that prove the theorem wrong? – 2016-02-15
-
0@LeBron This example is correct, but it doesn't prove the theorem wrong. The graph on the picture does contain a subdivision of $K_4$, you just need to look for it carefully. To see the subdivision, just erase any two edges incident with the central vertex. – 2016-02-15
-
0yes, thank you. I think i mixed up the concept of subgraph vs subdivision. – 2016-02-15
I think this is the example referred to by Jeremy Hurwitz (the "squash" corresponding to vertices 4,5,6,7)
A non-constructive counter-example comes from a theorem of Erdős: For any $\chi$ and $g$, there exists graphs of chromatic number at least $\chi$ and girth at least $g$. If we pick $g=\chi = 4$ then there exists a graph which is not $3$-colourable and is triangle free and therefore cannot possible contain a $K_4$ sub-graph.
Let $G$ be a square with one diagonal. Note that the opposite corners must have the same color in any 3-coloring. We can therefore use this gadget to replace any vertex of a graph without changing its 3-coloarability.
So, for example, we can take $K_4$ and replace one vertex with $G$ (connect two of the edges to one corner and the third edge to the other corner).
There's probably a smaller counter example.
-
1What's a squash? – 2012-10-31
-
0Sorry! That should have said "square with one diagonal". I've fixed it. – 2012-11-01