Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

While reasoning a bit on this question, I've tried to identify all the different reasons for which a graph $G = (V_G,E_G)$ may fail to be $k$ colorable. These are the only 2 reasons that I was able to identify so far:

  1. $G$ contains a clique of size $k+1$. This is the obvious reason.
  2. There exists a subgraph $H = (V_H, E_H)$ of $G$ such that both the following statements are true:

    • $H$ is not $k-1$ colorable.
    • $\exists x \in V_G - V_H\ \forall y \in V_H\ \{x,y\} \in E_G$. In other words there exists a node $x$ in $G$ but not in $H$, such that $x$ is connected to each node in $H$.

We can see the 2 reasons above as rules. By recursively applying them, the only 2 ways to build a non $k$ colorable graph which does not contain a $k+1$ clique are:

  1. Start from a cycle of even length (which is $2$ colorable), then apply rule 2 for $k-1$ times. Note that an edge is not considered to be a cycle of length $2$ (otherwise this process would have the effect of building a $k+1$ clique).
  2. Start from a cycle of odd length (which is $3$ colorable), then apply rule 2 for $k-2$ times. The length of the starting cycle must be greater than $3$ (otherwise this process would have the effect of building a $k+1$ clique).

Question

Is there any further reason, other than those 2 above, that makes a graph non $k$ colorable?

$\ $
Update 30/11/2012

More precisely, what I need is some theorem of the form:

A graph $G$ has chromatic number $\chi(G) = k + 1$ if and only if...

Hajós calculus, pointed out by Yuval Filmus in his answer, is a perfect example of what I am looking for, as a graph $G$ has chromatic number $\chi(G) = k + 1$ if and only if it can be derived from axiom $K_{k+1}$ by repeatedly applying the 2 rules of inference of the calculus. The Hajós number $h(G)$ is then the minimum number of steps necessary to derive $G$ (i.e. it is the length of the shortest proof).

It is very interesting that:

  • The question of whether there exists a graph $G$ whose $h(G)$ is exponential in the size of $G$ is still open.
  • If such $G$ does not exist, then $NP = coNP$.
share|improve this question
5  
I will repeat my comment from the question you link to in case you are not aware of the theorem (that everyone thinking about coloring should be) of Erdős: Given natural numbers g and k, there is a graph with girth at least g and chromatic number at least k. The girth of a graph is the size of the smallest cycle, meaning that if you have girth at least 3, every maximum clique is of size 2 (every edge is a maximum clique). –  Pål GD Nov 21 '12 at 23:06
2  
en.wikipedia.org/wiki/Hadwiger_conjecture_%28graph_theory%29 $\hspace{1.65 in}$ –  Ricky Demer Nov 21 '12 at 23:34
2  
A simple observation that is often helpful: Each colour class is an independent set. If you can show that there is no large independent set, then you know that you will need lots of colours. –  Jukka Suomela Nov 22 '12 at 0:26
1  
If there were always a simple reason for graphs to be non-$k$-colorable, the graph coloring problem would not be NP-hard. Unless P=NP, some graphs are non-$k$-colorable just because. –  JɛffE Nov 22 '12 at 4:03
5  
@JɛffE: a reason may be simple, but hard to compute. There's a pretty simple reason why a graph does or doesn't have a $k$-Clique, but it's still NP-hard. –  Luke Mathieson Nov 22 '12 at 5:33

5 Answers 5

up vote 26 down vote accepted

You should check the Hajós calculus. Hajós showed that every graph with chromatic number at least $k$ has a subgraph which has a "reason" for requiring $k$ colors. The reason in question is a proof system for requiring $k$ colors. The only axiom is $K_k$, and there are two rules of inference. See also this paper by Pitassi and Urquhart on the efficiency of this proof system.

share|improve this answer
1  
Excellent, this is what I was looking for. –  Giorgio Camerani Nov 26 '12 at 8:55
1  
Thanks for the pointer. Did not know about Hajos construction previously. –  Chandra Chekuri Nov 30 '12 at 14:54

A partial answer, in that I don't know a nice "reason" that can be generalised, but the following graph (shameless nicked from here):

Non-3-colorable graph with no K4 or odd cycle with a completely connected neighbour

Isn't 3-colorable, but is obviously 4-colorable (being planar), and it contains no $K_{4}$, nor any cycle with a additional vertex connected to all the cycle vertices (unless I'm missing something, but the only vertices connected to a vertex and its neighbour are in the 3-cycles). Taking it further, you could apply a version of rule 2 to get a graph of chromatic number 5.

I would suspect that for any given genus, there's a graph of a certain minimum chromatic number (see the Heawood conjecture) that doesn't follow rules 1 or 2. Of course I have no proof other than intuition.

share|improve this answer
    
The Petersen Graph is a smaller example of the same thing. Both the above and the Petersen Graph have $K_4$ minors, though, which goes back to the above comment about Hadwiger's. –  William Macrae Nov 22 '12 at 4:47
1  
The Hadwiger Conjecture though is a necessary condition, but not sufficient, so a graph has chromatic number $k$ iff it has a $K_{k}$ minor and something else. As JeffE points out of course, it's likely that the something else is just because (in the sense that it's not a simple answer). –  Luke Mathieson Nov 22 '12 at 5:24
    
@LukeMathieson: Extremely interesting. Do you have an example of a graph which has a $K_k$ minor and which is $k-1$ colorable? –  Giorgio Camerani Nov 22 '12 at 11:20
5  
Take a $K_{k}$ and subdivide all the edges. The resulting graph is bipartite and thus two color able, but obviously has the complete graph as a minor. –  Luke Mathieson Nov 22 '12 at 13:13

Lovasz found topological obstructions for k-colorability and used his theory to solve Knaser's conjecture. His theorem is the following. Let G be a connected graph, and let N(G) be a simplicial complex whose faces are subsets of V that have a common neighbors. Then if N(K) is k-connected (namely, all its reduced homology groups are 0 up to dimension k-1) then the number of colors needed to color G is at least k+3.

share|improve this answer

Not having a large independent set can be as important as having a large clique.

An important obstruction for a graph to be non k-colorable is that the maximum size of an independent set is smaller than n/k, where n is the number of vertices. This is a very important obstraction. For example it implies that a random graph in G(n,1/2) has chromatic number at least n/log n.

A more refine obstruction is that for every assignment of nonnegative weights for the vertices there is no independent set that capture a fraction 1/5 (or more) of the total weight. Note that this also include the "no clique obstructions." LP-duality tells you that this obstruction is equivalent to the "fractional chromatic number" of G being larger than k.

There are also obstructions for k-colorability of a different nature that sometimes go beyond the fractional chromatic number barrier. I will devote a separate asnwer to them.

share|improve this answer
    
Thanks for your answer! The more refined obstruction binding weights and independent sets is extremely interesting... –  Giorgio Camerani Dec 1 '12 at 20:51

Re your reformulation of the question as "More precisely, what I need is some theorem of the form: A graph $G$ has chromatic number $\chi(G)=k+1$ if and only if...":

I don't know whether you will think this is adequately explanatory, but it at least fits the syntax you request: an undirected graph $G$ has chromatic number $\chi(G)\ge k$ if and only if, no matter how you orient the edges of $G$, the resulting directed graph will include at least one directed path of length $k-1$. This is the Gallai–Hasse–Roy–Vitaver theorem.

share|improve this answer
    
Thanks! This is definitely 100% adequate. It perfectly fits the reformulation of the question. –  Giorgio Camerani Dec 2 '12 at 9:20

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.