Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
In 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)$). –  Jeremy Hurwitz Oct 31 '12 at 7:08

4 Answers 4

up vote 9 down vote accepted

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.

Wheel graph

share|improve this answer
    
@Douglas S. Stones This is offtopic, but what software did you use to draw the diagram? –  Dan Shved Nov 2 '12 at 12:15
    
I pinched it from Wikipedia: here; listed as "Released into the public domain (by the author)." It would be possible to draw it this way using tikz. –  Douglas S. Stones Nov 2 '12 at 21:56

I think this is the example referred to by Jeremy Hurwitz (the "squash" corresponding to vertices 4,5,6,7)

enter image description here

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
1  
What's a squash? –  EuYu Oct 31 '12 at 7:09
    
Sorry! That should have said "square with one diagonal". I've fixed it. –  Jeremy Hurwitz Nov 1 '12 at 15:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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