21
$\begingroup$

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$.
Improve this question
$\endgroup$
9
  • 5
    $\begingroup$ 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). $\endgroup$
    – John Kemeny
    Commented Nov 21, 2012 at 23:06
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Hadwiger_conjecture_%28graph_theory%29 $\hspace{1.65 in}$ $\endgroup$
    – user6973
    Commented Nov 21, 2012 at 23:34
  • 2
    $\begingroup$ 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. $\endgroup$
    – Jukka Suomela
    Commented Nov 22, 2012 at 0:26
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Commented Nov 22, 2012 at 4:03
  • 5
    $\begingroup$ @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. $\endgroup$
    – Luke Mathieson
    Commented Nov 22, 2012 at 5:33

5 Answers 5

Reset to default
29
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Excellent, this is what I was looking for. $\endgroup$
    – Giorgio Camerani
    Commented Nov 26, 2012 at 8:55
  • 1
    $\begingroup$ Thanks for the pointer. Did not know about Hajos construction previously. $\endgroup$
    – Chandra Chekuri
    Commented Nov 30, 2012 at 14:54
15
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – William Macrae
    Commented Nov 22, 2012 at 4:47
  • 1
    $\begingroup$ 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). $\endgroup$
    – Luke Mathieson
    Commented Nov 22, 2012 at 5:24
  • $\begingroup$ @LukeMathieson: Extremely interesting. Do you have an example of a graph which has a $K_k$ minor and which is $k-1$ colorable? $\endgroup$
    – Giorgio Camerani
    Commented Nov 22, 2012 at 11:20
  • 5
    $\begingroup$ 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. $\endgroup$
    – Luke Mathieson
    Commented Nov 22, 2012 at 13:13
12
$\begingroup$

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.

Improve this answer
$\endgroup$
11
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for your answer! The more refined obstruction binding weights and independent sets is extremely interesting... $\endgroup$
    – Giorgio Camerani
    Commented Dec 1, 2012 at 20:51
11
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks! This is definitely 100% adequate. It perfectly fits the reformulation of the question. $\endgroup$
    – Giorgio Camerani
    Commented Dec 2, 2012 at 9:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.