<p>You might be interested in the colouring number, which is 1 plus the maximum over all subgraphs $H$, of the minimum degree of $H$.  It can be computed efficiently, and is an upper bound for the chromatic number.</p>

<p><a href="http://en.wikipedia.org/wiki/Colouring_number#Algorithms">http://en.wikipedia.org/wiki/Colouring_number#Algorithms</a></p>

CC BY-SA 3.0
2011-10-19T19:36:11.297Z
Minor correction: it is not true that the coloring number equals the least number of colors in a greedy coloring. If you order the vertices according to their colors in an optimal coloring (with the additional property that the first color class is maximal, and the second is maximal in the remaining graph etc) then the greedy algorithm will find the same optimal coloring.
David Eppstein
CC BY-SA 3.0
2011-10-19T19:20:35.363Z
2011-10-19T19:39:20.027Z
2011-10-19T19:39:20.027Z
Andrew D. King
<p>Compute a maximum matching in the complement of the input graph. Every unmatched node must be in a different color class in any coloring. So: if you get at least cn matched edges, then the matching itself gives you a coloring with an upper bound of (1-c)n, and an approximation ratio of 64(1-c). If you don't get at least cn edges, then you get a lower bound of (1 - 2c)n colors and an approximation ratio of 1/(1-2c). Solving the equation 64(1-c) = 1/(1-2c) leads to an approximation ratio slightly larger than 32; see Sasho Nikolov's comment for the precise value.</p>

CC BY-SA 3.0
2011-10-19T17:01:14.233Z
small correcion: in the first case the upper bound is (1-c)n and the lower bound is n/64, so the approx ratio is (1-c)64. When you solve (1-c)64 = 1/(1-2c), you get $c = 3/16 (4-\sqrt{2}) \approx 0.5$ and approximation ratio $\approx 32$. Seems like given an upper bound of $k$ for $\alpha(G)$, this method gives an approximation ratio that goes to $\frac{k}{2}$ as $k$ goes to infinity.
Sasho Nikolov
CC BY-SA 3.0
2011-10-19T16:24:46.727Z
2011-10-20T01:13:43.063Z
2011-10-20T01:13:43.063Z
David Eppstein
<p>In my job the following problem arises:</p>

<p>Is there a known algorithm, that approximates the chromatic number of a graph without an independent set of order 65? (So alpha(G)&lt;=64 is known and |V|/64 is a trivial lower, |V| a trivial upper bound. But are there better proven approximations under this special condition?) </p>

<p>What if we relax to the fractional chromatic number? And to "good" running times in average cases?</p>

CC BY-SA 3.0
2011-10-19T13:20:50.017Z
Independent set? Don't you mean clique?
Tyson Williams
CC BY-SA 3.0
2011-10-19T13:25:56.370Z
No, we have the condition, that in the inverse graph there is no clique of order >=65. So here there is no independent set of this size and every colour set could contain at maximum only 64 vertices.
cyrix42
CC BY-SA 3.0
2011-10-19T13:57:55.400Z
I think this is an excellent question for this site; let's hope that someone has a good answer.
Jukka Suomela
CC BY-SA 3.0
2011-10-19T14:05:48.850Z
Where in the question does it talk about the inverse graph?
Tyson Williams
CC BY-SA 3.0
2011-10-19T14:13:27.443Z
@TysonWilliams: I think the question is perfectly clear. Forget the comment, re-read the question. :)
Jukka Suomela
CC BY-SA 3.0
2011-10-19T16:04:22.203Z
The funny thing is, this conditions guarantees that the trivial approximation is a 64-approximation to the optimum. I wonder whether just the promise of a small independence number can give a better algorithm.
Sasho Nikolov
CC BY-SA 3.0
2011-10-19T16:21:21.630Z
@SashoNikolov exactly. that's what makes it interesting
Suresh Venkat
CC BY-SA 3.0
2011-10-19T17:16:12.817Z
Is the problem motivated by practical application? If so, one should focus on interesting heuristics that are going to do well - improving the trivial 64 approximation is not that interesting.
Chandra Chekuri
CC BY-SA 3.0
2011-10-19T19:28:15.410Z
There is no better upper bound unless we are guaranteed that there actually exists a stable set of size 64, in which case $|V|-63$ is a trivial upper bound.  And then, since the rest of the graph can be a clique complete to the stable set, this is the best possible upper bound.
Andrew D. King
CC BY-SA 3.0
2011-10-20T05:22:59.700Z
@Chandra Chekuri: Yes, the problem is motivated by practical application. In fact we are searching for vertex clique partition in the inverse graph; which is equivalent to these better studied problem (a clique in the inverse graph corresponds to a colour set).
cyrix42
CC BY-SA 3.0
2011-10-20T05:31:18.543Z
So, yes, we are searching for practical algorithms (so running time should be in average case manageable) with known approximation ratio (with high probability as |V| --> oo): How good is our heuristic or are there still better ones?
cyrix42
CC BY-SA 3.0
2011-10-21T10:48:53.910Z
Regarding the fractional chromatic number: You have only polynomially many independent sets; hence you can formulate a polynomially large LP and solve it in polynomial time. In summary, you can find the exact answer in polynomial time. (And all of these polynomials are impractical.)
Jukka Suomela
CC BY-SA 3.0
2011-10-21T12:08:41.457Z
By the way, if you want to find good approximations of the fractional chromatic number quickly, it is sufficient to find good approximations of max-weight independent sets quickly. Hence this suggest a new question: If we know that the largest independent set has size 64, is there an algorithm that finds *good* approximations of max-weight independent sets *much* faster than the trivial $O(n^{64})$-time algorithm?
Jukka Suomela
CC BY-SA 3.0
2011-10-21T13:22:52.737Z
@Jukka Suomela : Thanks for answer. :) But the LP is way too large...
cyrix42
<ds.algorithms><graph-algorithms><approximation-algorithms><graph-colouring>
Approximate graph colouring  with a promised upper bound on maximum independent set
cyrix42
# Approximate graph colouring  with a promised upper bound on maximum independent set

(Asked by: username_0 on 2011-10-19)

In my job the following problem arises:

Is there a known algorithm, that approximates the chromatic number of a graph without an independent set of order 65? (So alpha(G)<=64 is known and |V|/64 is a trivial lower, |V| a trivial upper bound. But are there better proven approximations under this special condition?)

What if we relax to the fractional chromatic number? And to "good" running times in average cases?

**Tags:** ds.algorithms, graph-algorithms, approximation-algorithms, graph-colouring

> **Comments:**
> **username_1**: Independent set? Don't you mean clique?  
> **username_0**: No, we have the condition, that in the inverse graph there is no clique of order >=65. So here there is no independent set of this size and every colour set could contain at maximum only 64 vertices.  
> **username_2**: I think this is an excellent question for this site; let's hope that someone has a good answer.  
> **username_1**: Where in the question does it talk about the inverse graph?  
> **username_2**: @TysonWilliams: I think the question is perfectly clear. Forget the comment, re-read the question. :)  
> **username_3**: The funny thing is, this conditions guarantees that the trivial approximation is a 64-approximation to the optimum. I wonder whether just the promise of a small independence number can give a better algorithm.  
> **username_4**: @SashoNikolov exactly. that's what makes it interesting  
> **username_5**: Is the problem motivated by practical application? If so, one should focus on interesting heuristics that are going to do well - improving the trivial 64 approximation is not that interesting.  
> **username_6**: There is no better upper bound unless we are guaranteed that there actually exists a stable set of size 64, in which case $|V|-63$ is a trivial upper bound.  And then, since the rest of the graph can be a clique complete to the stable set, this is the best possible upper bound.  
> **username_0**: @username_5: Yes, the problem is motivated by practical application. In fact we are searching for vertex clique partition in the inverse graph; which is equivalent to these better studied problem (a clique in the inverse graph corresponds to a colour set).  
> **username_0**: So, yes, we are searching for practical algorithms (so running time should be in average case manageable) with known approximation ratio (with high probability as |V| --> oo): How good is our heuristic or are there still better ones?  
> **username_2**: Regarding the fractional chromatic number: You have only polynomially many independent sets; hence you can formulate a polynomially large LP and solve it in polynomial time. In summary, you can find the exact answer in polynomial time. (And all of these polynomials are impractical.)  
> **username_2**: By the way, if you want to find good approximations of the fractional chromatic number quickly, it is sufficient to find good approximations of max-weight independent sets quickly. Hence this suggest a new question: If we know that the largest independent set has size 64, is there an algorithm that finds *good* approximations of max-weight independent sets *much* faster than the trivial $O(n^{64})$-time algorithm?  
> **username_0**: @username_2 : Thanks for answer. :) But the LP is way too large...  

---

## 2 answers

### Answer by username_7 on 2011-10-19. Score: 12 | Accepted answer

Compute a maximum matching in the complement of the input graph. Every unmatched node must be in a different color class in any coloring. So: if you get at least cn matched edges, then the matching itself gives you a coloring with an upper bound of (1-c)n, and an approximation ratio of 64(1-c). If you don't get at least cn edges, then you get a lower bound of (1 - 2c)n colors and an approximation ratio of 1/(1-2c). Solving the equation 64(1-c) = 1/(1-2c) leads to an approximation ratio slightly larger than 32; see username_3's comment for the precise value.

> **Comments:**
> **username_3**: small correcion: in the first case the upper bound is (1-c)n and the lower bound is n/64, so the approx ratio is (1-c)64. When you solve (1-c)64 = 1/(1-2c), you get $c = 3/16 (4-\sqrt{2}) \approx 0.5$ and approximation ratio $\approx 32$. Seems like given an upper bound of $k$ for $\alpha(G)$, this method gives an approximation ratio that goes to $\frac{k}{2}$ as $k$ goes to infinity.  

---

### Answer by username_6 on 2011-10-19. Score: 5

You might be interested in the colouring number, which is 1 plus the maximum over all subgraphs $H$, of the minimum degree of $H$. It can be computed efficiently, and is an upper bound for the chromatic number.

<http://en.wikipedia.org/wiki/Colouring_number#Algorithms>

> **Comments:**
> **username_7**: Minor correction: it is not true that the coloring number equals the least number of colors in a greedy coloring. If you order the vertices according to their colors in an optimal coloring (with the additional property that the first color class is maximal, and the second is maximal in the remaining graph etc) then the greedy algorithm will find the same optimal coloring.  

---

