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?
Tell me more
×
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.
|
|
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.
|
|||||
|
|
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. |
|||||||
|
