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.

I have recently been introduced to graph theory, and there is that one idea I have which I am struggling with. I would like to know if this is true, and whether or not there is a somewhat simple proof for it (or for some of the simpler cases). By colorable with $n$ colors I mean that the vertices can be colored so that no two adjacent vertices are of the same color.

Can we say that a graph is colorable with $k$ colors if and only if there is no $k+1$ vertices complete subgraph to it?

It is simple for the implication, but for the other way, I feel like there are many subtle situations I am not able to grasp. I have also tried to find counter-examples, by creating "locked" graphs in which the colors can't be interchanged and then introducing new vertices, but without success.

I am also interested in the simple cases, for which I also have no clue, such as when $k=2$.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

No, this doesn't work. Take, for instance, a cycle on five vertices; it certainly doesn't contain a triangle (complete graph on three vertices), but it requires at least three colors.

share|improve this answer

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.