# Reasons for which a graph may be not $k$ colorable?

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$.
-
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
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
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. – Jeffε Nov 22 '12 at 4:03
@JɛﬀE: 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

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.

-
Excellent, this is what I was looking for. – Giorgio Camerani Nov 26 '12 at 8:55
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):

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.

-
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
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
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.

-

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.

-
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.

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