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

CC BY-SA 3.0
2012-12-01T20:10:07.167Z
2012-12-01T20:10:07.167Z
Gil Kalai
<p>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...":</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Gallai%E2%80%93Hasse%E2%80%93Roy%E2%80%93Vitaver_theorem" rel="noreferrer">Gallai–Hasse–Roy–Vitaver theorem</a>.</p>

CC BY-SA 3.0
2012-12-02T09:20:44.297Z
Thanks! This is definitely 100% adequate. It perfectly fits the reformulation of the question.
Giorgio Camerani
CC BY-SA 3.0
2012-12-02T04:10:37.000Z
2012-12-02T16:39:33.643Z
2012-12-02T16:39:33.643Z
David Eppstein
<p>Not having a large independent set can be as important as having a large clique.</p>

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

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

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

CC BY-SA 3.0
2012-12-01T20:51:32.930Z
Thanks for your answer! The more refined obstruction binding weights and independent sets is extremely interesting...
Giorgio Camerani
CC BY-SA 3.0
2012-12-01T19:35:26.250Z
2012-12-01T19:35:26.250Z
Gil Kalai
<p>A partial answer, in that I don't know a nice "reason" that can be generalised, but the following graph (shameless nicked from <a href="http://math.la.asu.edu/~checkman/Steinberg.html" rel="nofollow noreferrer">here</a>):</p>

<p><img src="https://i.sstatic.net/mCg5c.jpg" alt="Non-3-colorable graph with no K4 or odd cycle with a completely connected neighbour"></p>

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

<p>I would suspect that for any given genus, there's a graph of a certain minimum chromatic number (see the <a href="http://en.wikipedia.org/wiki/Heawood_conjecture" rel="nofollow noreferrer">Heawood conjecture</a>) that doesn't follow rules 1 or 2. Of course I have no proof other than intuition.</p>

CC BY-SA 3.0
2012-11-22T04:47:32.270Z
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
CC BY-SA 3.0
2012-11-22T05:24:31.067Z
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
CC BY-SA 3.0
2012-11-22T11:20:47.580Z
@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
CC BY-SA 3.0
2012-11-22T13:13:07.153Z
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
CC BY-SA 3.0
2012-11-22T01:06:46.743Z
2012-11-22T01:06:46.743Z
Luke Mathieson
<p>You should check the <a href="http://en.wikipedia.org/wiki/Haj%C3%B3s_construction">Hajós calculus</a>. Hajós showed that every graph with chromatic number at least $k$ has a <em>subgraph</em> 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 <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.5879">this paper</a> by Pitassi and Urquhart on the efficiency of this proof system.</p>

CC BY-SA 3.0
2012-11-26T08:55:07.140Z
Excellent, this is what I was looking for.
Giorgio Camerani
CC BY-SA 3.0
2012-11-30T14:54:13.240Z
Thanks for the pointer. Did not know about Hajos construction previously.
Chandra Chekuri
CC BY-SA 3.0
2012-11-25T17:13:13.760Z
2013-01-20T16:42:33.293Z
2013-01-20T16:42:33.293Z
Yuval Filmus
<p>While reasoning a bit on <a href="https://cstheory.stackexchange.com/questions/14319/natural-clique-to-k-color-reduction">this question</a>, 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:</p>

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

<ul>
<li>$H$ is not $k-1$ colorable.</li>
<li>$\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$.</li>
</ul></li>
</ol>

<p>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:</p>

<ol>
<li>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).</li>
<li>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).</li>
</ol>

<blockquote>
  <p><strong>Question</strong>  </p>
  
  <p>Is there any further reason, other than those 2 above, that makes a graph non $k$ colorable?</p>
</blockquote>

<p>$\ $<br>
<strong>Update 30/11/2012</strong>    </p>

<p>More precisely, what I need is some theorem of the form:</p>

<blockquote>
  <p>A graph $G$ has chromatic number $\chi(G) = k + 1$ if and only if...</p>
</blockquote>

<p><a href="http://en.wikipedia.org/wiki/Haj%C3%B3s_construction" rel="nofollow noreferrer">Hajós calculus</a>, 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).</p>

<p>It is very interesting that:</p>

<ul>
<li>The question of whether there exists a graph $G$ whose $h(G)$ is exponential in the size of $G$ is still open.</li>
<li>If such $G$ does not exist, then $NP = coNP$.</li>
</ul>

CC BY-SA 3.0
2012-11-21T23:06:26.987Z
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).
John K.
CC BY-SA 3.0
2012-11-22T00:26:07.627Z
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
CC BY-SA 3.0
2012-11-22T04:03:51.730Z
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ε
CC BY-SA 3.0
2012-11-22T05:33:58.957Z
@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
CC BY-SA 3.0
2012-11-22T16:55:11.180Z
@LukeMathieson. There is a difference between clique and coloring. 3-coloring is NP-Complete while k-Clique is in P for every fixed value of k.
Chandra Chekuri
CC BY-SA 3.0
2012-11-22T21:47:29.497Z
@ChandraChekuri, indeed, Clique is only W[1]-complete, whereas $k$-COL is Para-NP-complete, they're drastically different, it's just worth keeping in mind that simple to compute is not the same as simple.
Luke Mathieson
CC BY-SA 3.0
2012-11-22T22:24:32.353Z
I should say easy or efficient to compute, rather than simple. It's simple enough to compute whether there's a $k$-clique, just not very fast.
Luke Mathieson
CC BY-SA 4.0
2023-12-16T01:26:58.100Z
"If such G does not exist, then NP=coNP." Should not it only imply a much weaker result, that nETH fails? Because shorter than exponential is not necessarily polynomial.
rus9384
<graph-theory><co.combinatorics><graph-colouring><clique>
Reasons for which a graph may be not $k$ colorable?
Giorgio Camerani
# Reasons for which a graph may be not $k$ colorable?

(Asked by: username_0 on 2012-11-21)

While reasoning a bit on [this question](https://cstheory.stackexchange.com/questions/14319/natural-clique-to-k-color-reduction), 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](http://en.wikipedia.org/wiki/Haj%C3%B3s_construction), 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$.

**Tags:** graph-theory, co.combinatorics, graph-colouring, clique
> **Comments:**
> **username_1**: 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).  
> **username_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.  
> **username_3**: 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_.  
> **username_4**: @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.  
> **username_5**: @LukeMathieson. There is a difference between clique and coloring. 3-coloring is NP-Complete while k-Clique is in P for every fixed value of k.  
> **username_4**: @ChandraChekuri, indeed, Clique is only W[1]-complete, whereas $k$-COL is Para-NP-complete, they're drastically different, it's just worth keeping in mind that simple to compute is not the same as simple.  
> **username_4**: I should say easy or efficient to compute, rather than simple. It's simple enough to compute whether there's a $k$-clique, just not very fast.  
> **username_6**: "If such G does not exist, then NP=coNP." Should not it only imply a much weaker result, that nETH fails? Because shorter than exponential is not necessarily polynomial.  

---

## 5 answers

### Answer by username_10 on 2012-11-25. Score: 29 | Accepted answer

You should check the [Hajós calculus](http://en.wikipedia.org/wiki/Haj%C3%B3s_construction). 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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.5879) by Pitassi and Urquhart on the efficiency of this proof system.

> **Comments:**
> **username_0**: Excellent, this is what I was looking for.  
> **username_5**: Thanks for the pointer. Did not know about Hajos construction previously.  

---

### Answer by username_4 on 2012-11-22. Score: 15

A partial answer, in that I don't know a nice "reason" that can be generalised, but the following graph (shameless nicked from [here](http://math.la.asu.edu/~checkman/Steinberg.html)):

![Non-3-colorable graph with no K4 or odd cycle with a completely connected neighbour](https://i.sstatic.net/mCg5c.jpg)

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](http://en.wikipedia.org/wiki/Heawood_conjecture)) that doesn't follow rules 1 or 2. Of course I have no proof other than intuition.

> **Comments:**
> **username_9**: 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.  
> **username_4**: 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).  
> **username_0**: @LukeMathieson: Extremely interesting. Do you have an example of a graph which has a $K_k$ minor and which is $k-1$ colorable?  
> **username_4**: 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.  

---

### Answer by username_7 on 2012-12-01. Score: 12

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.


---

### Answer by username_8 on 2012-12-02. Score: 11

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](http://en.wikipedia.org/wiki/Gallai%E2%80%93Hasse%E2%80%93Roy%E2%80%93Vitaver_theorem).

> **Comments:**
> **username_0**: Thanks! This is definitely 100% adequate. It perfectly fits the reformulation of the question.  

---

### Answer by username_7 on 2012-12-01. Score: 11

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.

> **Comments:**
> **username_0**: Thanks for your answer! The more refined obstruction binding weights and independent sets is extremely interesting...  

---

