17
$\begingroup$

I am trying to find a good lower bound for chromatic number of one family of graphs. I'm curious what are the known lower bounds for chromatic number. There are two obvious: $\chi(G) \geq \omega(G)$ and $\chi(G) \geq n / \alpha(G)$. One can also employ fancy Lovasz theta-function.

Chromatic number of Kneser graph can be obtained by the means of topological combinatorics (particularly, using Borsuk-Ulam theorem). But it is not clear if this method is general enough.

So, what are the more or less general techniques for lowerbounding chromatic number?

Improve this question
$\endgroup$
3
  • $\begingroup$ Just one graph? Can't you just explicitly compute the chromatic polynomial? $\endgroup$
    – Qiaochu Yuan
    Commented Jul 29, 2010 at 17:48
  • $\begingroup$ I'm sorry, one family of graphs. Anyway, they are way too big. $\endgroup$
    – ilyaraz
    Commented Jul 29, 2010 at 18:15
  • 2
    $\begingroup$ The theta function can be found in polynomial time, unlike the two other bounds you suggest. As Suresh commented, it can be expressed as the solution of a semi-definite program, and can therefore be found using linear algebra. Moreover, theta is also the Shannon capacity of the (channel corresponding to the) graph. So I'd hesitate in dismissing it as "fancy"... $\endgroup$
    – András Salamon
    Commented Jul 30, 2010 at 10:35

6 Answers 6

Reset to default
13
$\begingroup$

Hoffman's bound states that $\chi(G) \geq 1 - \frac{\lambda_1(G)}{\lambda_n(G)}$ where $\lambda_1(G), \lambda_n(G)$ denote the largest and smallest eigenvalues of the adjacency matrix of $G$. (Note that $\lambda_n(G)$ is negative.)

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ For a quick discussion with references, see Yonatan Bilu, Tales of Hoffman: Three extensions of Hoffman's bound on the graph chromatic number, Journal of Combinatorial Theory, Series B 96 (2006) dx.doi.org/10.1016/j.jctb.2005.10.002 $\endgroup$
    – András Salamon
    Commented Jul 30, 2010 at 11:22
  • $\begingroup$ Thank you. Miserably, this bound is too rough. Anyway, it is nice. $\endgroup$
    – ilyaraz
    Commented Jul 30, 2010 at 17:08
11
$\begingroup$

Lovasz's topological lower bounds on chromatic number were extended by Babson and Kozlov -- they have a series of articles, all available on the arXiv. A nice place to start is "Complexes of Graph Homomorphisms."

There are also lower bounds on chromatic number coming from statistical physics -- see Brightwell and Winkler's "Graph homomorphisms and long range action."

All that said, it seems that one has to be a bit lucky for these methods to be applicable. See for example, "Neighborhood complex of a random graph," where it shown that topological lower bounds are very far from chromatic number for almost all graphs.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you. And do you happen to know any general techniques to estimate theta-function? $\endgroup$
    – ilyaraz
    Commented Jul 29, 2010 at 19:43
  • 1
    $\begingroup$ I don't know any general techniques to estimate the theta-function. However there are other, easier to compute, spectral lower bounds on chromatic number. In particular, see Theorem 5.2 of these notes: tinyurl.com/297vtgk $\endgroup$
    – Matthew Kahle
    Commented Jul 29, 2010 at 22:23
  • 2
    $\begingroup$ Since the theta function can be written as the solution to a semidefinite program (www-math.mit.edu/~goemans/…) maybe that can help in your problem ? $\endgroup$
    – Suresh Venkat
    Commented Jul 30, 2010 at 2:24
  • 1
    $\begingroup$ For details about how to compute the theta function, see L. Lovász: Semidefinite programs and combinatorial optimization, in: Recent Advances in Algorithms and Combinatorics 11, Springer (2003), 137-194. cs.elte.hu/~lovasz/semidef.ps $\endgroup$
    – András Salamon
    Commented Jul 30, 2010 at 10:41
  • $\begingroup$ Matthew, thank you for these references. $\endgroup$
    – András Salamon
    Commented Aug 1, 2010 at 2:28
6
$\begingroup$

I discussed this issue with Stefano Gualandi a few days ago while setting up this page: http://sites.google.com/site/graphcoloring/vertex-coloring

As evidenced from the results in the web page, for arbitrary graphs of large size the best lower bound is often found by the fractional chromatic number.

This number is found by solving the linear relaxation of the integer programming formulation of the chromatic number problem. You find it, for example, here: http://www.optimization-online.org/DB_HTML/2005/12/1257.html eq. 11-13.

Computationally, you have to find a collection of maximal stable sets that covers all vertices (some may be included more than once), and then solve the corresponding LP relaxation of the chromatic number problem. The computational burden lays in the fact that the collection contains an exponential number of elements. The fractional chromatic number problem is also NP-hard.

However, there are techniques that can avoid generating all maximal stable sets. See for example: http://www.optimization-online.org/DB_HTML/2010/03/2568.html Alternatively, some stable sets chosen heuristically can be used but the result of the LP will not be the fractional chromatic number in this case.

If you need computational results and cannot find a way to obtain them yourself you can write to Stefano (who has all programs).

Improve this answer
$\endgroup$
3
  • $\begingroup$ It seems interesting. The first graph of my family is of 560 vertices. Is fractional chromatic bound tractable on such graph sizes? $\endgroup$
    – ilyaraz
    Commented Jul 30, 2010 at 17:10
  • 2
    $\begingroup$ But computing the fractional chromatic number is also NP-hard. $\endgroup$
    – Chris Godsil
    Commented Jul 30, 2010 at 17:51
  • 1
    $\begingroup$ In this article, table 4, optimization-online.org/DB_HTML/2010/03/2568.html there are results for a time bound of 3600 seconds. Whether the fractional chromatic number problem for a graph of 560 vertices can be solved within this time bound depends on the type of graph. From the table it seems that denser graphs are more likely to be solved earlier. $\endgroup$
    – Marco Chiarandini
    Commented Aug 1, 2010 at 16:25
5
$\begingroup$

Short of the two lower bounds you gave, there is only one other I could think of, and it may be hard to use, depending on what your family of graphs is... It is the following : Build a coloring of your graph by first taking a maximum independent set, then taking another maximum independent set in the rest of the graph, then taking another one, ....

You will obtain this way a non-optimal coloring, but it can be proved (consequence of the log(n) approximation of the set cover problem : http://en.wikipedia.org/wiki/Set_cover_problem ), that the number of classes you finally use it at most log(n) times the Chromatic number.

Well, if your graphs are nice enough for you to compute explicitly a coloring this way using k classes, you will be able to say $\chi(G)\geq k/log(n)$. Of course, there is no meaning in doing this if you do not expect the chromatic number to be very large !

Could you give some other information on your family of graphs, or are they too "hand-made" for that ? :-)

Nathann

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ I don't understand the link with Set Cover? You are essentially proposing a greedy algorithm, and this is known to require up to $n$ colours for crowns with $n^2$ vertices (which are bipartite). For crowns, this would yield a lower bound of $n/\log n$ instead of the actual value of 2. en.wikipedia.org/wiki/Greedy_coloring $\endgroup$
    – András Salamon
    Commented Jul 30, 2010 at 10:59
  • $\begingroup$ If it was right, there would be no result about inapproximability within $n^{1 - \epsilon}$ factor. Anyway, thank you. $\endgroup$
    – ilyaraz
    Commented Jul 30, 2010 at 17:36
  • 1
    $\begingroup$ This algorithm requires to find at each step a "Maximum Independent Set", which is a NP-Complete problem ! This is a contradiction only if you can do that in polynomial time ;-) Nathann $\endgroup$
    – Nathann Cohen
    Commented Jul 31, 2010 at 2:36
  • 1
    $\begingroup$ Aha, Nathann you are not proposing maximal independent sets, but actually going to the trouble of finding the maximum ones (I misinterpreted what you meant as it seemed too audacious). Interesting idea! If one wants algorithms, then is computing successive independent sets actually going to beat out just computing a best colouring? Finding a maximum independent set can be done in something like $O(2^{0.304n})$ time if I remember correctly. Perhaps to make progress here ilyaraz really needs to say more about the problem -- is a closed-form bound sought, or a computable one? $\endgroup$
    – András Salamon
    Commented Aug 1, 2010 at 2:19
  • 3
    $\begingroup$ If one is just interested in theoretical bounds, then perhaps his family is nice enough to compute or bound somewhat efficiently the size of Max Independent Sets. If he is interested in patrice, well..I have been working on Sage (sagemath.org) for a year, and we have inside a software called Cliquer (users.tkk.fi/pat/cliquer.html) which I find very fast. The Coloring algorithms sadly, are way slower.**Anyone having an efficient implementation of one, or the idea of an algorithm in mind has my immediate attention, my respect, and perhaps even some money if he/she asks!** $\endgroup$
    – Nathann Cohen
    Commented Aug 1, 2010 at 6:12
5
$\begingroup$

Determining the chromatic number of an $n$-vertex graph is NP-Complete, and even approximating the chromatic number within an $NP^{1-\epsilon}$ ratio is $NP$-hard for every fixed $\epsilon>0$ (see http://en.wikipedia.org/wiki/Graph_coloring#Computational_complexity ). This means that assuming $ P\ne NP$ (which is consider a very reasonable conjecture by many in complexity theory) that no lower bound algorithm exists that is - general, as it works on all graphs - efficient, as it gives a lower bound in runtime polynomial in the size of the graph - good, as in it comes close to the true lower bound

So in a way, the best algorithm that computes a lower-bound efficiently is the trivial algorithm that always outputs 1 or 2 (as we can decide 2-colorability).

In of itself, that above isn't terrible for your purposes because in a sense all one needs for a lower-bound proof is a certificate that the given family of graphs has high chromatic number. However, assuming $NP\ne coNP$ (another plausible conjecture), there cannot be a proof system such that: - general, as it works for all graphs - small, in the sense that it is of size polynomial in the size of the graph - good, as for all graphs with chromatic number >=4 the proof system lower bounds the chromatic number likewise

(This last point follows from the fact that even determining if a graph is 3-colorable is $NP$-Complete.)

So in a sense, there can't be "general lower-bound technique" but rather only a collection of ad-hoc methods.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Since the various bounds are all decidable most mathematicians would perhaps be happy with them, even if they are hard to compute? $\endgroup$
    – András Salamon
    Commented Jul 30, 2010 at 11:14
  • 2
    $\begingroup$ As was pointed out to me later, the $n^{1-\epsilon}$ inapproximability result also extends to the certificate case, so even approximate lower-bound techniques are ruled out by the assumption that $NP\ne coNP$. One caveat is this machinery is for graphs with large chromatic number (ie. growing as $n^{\delta}$ for some $\delta>0$), it is not currently known how hard it is to distinguish 3-colorable graphs from 100-colorable graphs. $\endgroup$
    – miforbes
    Commented Jul 30, 2010 at 14:25
  • 2
    $\begingroup$ To address And\'{a}s' comment, even though everything is still decidable in the above, and so in principle could be used for a mathematical proof, the fact of the matter is that most proof techniques in combinatorics (that I know of) yield certificates that are "small" with respect to the problem. Another perspective however is that enumeration over all possible colorings is a valid way of deciding if a graph is $k$-colorable, but is practically useless for the purpose of a proof because it takes exponential time and has little structure to work with. $\endgroup$
    – miforbes
    Commented Jul 30, 2010 at 15:52
  • 2
    $\begingroup$ I suppose then one of the various ad-hoc methods might work, but it seems unlikely that an (as-yet-unknown) "general" method might work. As an aside, that is a fair tight bound that you have already - how did you prove it? Does that method not give the "correct" answer already? $\endgroup$
    – miforbes
    Commented Jul 31, 2010 at 14:27
  • 1
    $\begingroup$ I have a $\Theta(\log n)$-gap and what I want is to close it. These clique and independent set bounds are obvious in this case, and upper bound is obtained by the means of the probabilistic method. $\endgroup$
    – ilyaraz
    Commented Aug 1, 2010 at 22:09
3
$\begingroup$

Knowing more about your graph class would be very helpful. I know Bill Cook and Stephan Held are doing some work on lower-bounding $\chi$ using LP duality and branch-and-bound. Basically they look for a lower bound on the fractional chromatic number by finding a reasonably good feasible solution for the dual LP, i.e. a fractional clique.

A fractional clique is just a non-negative vertex weighting on the graph so that no stable set has weight more than 1. The total weight of a fractional clique is a lower bound for the fractional chromatic number, and so is in turn a lower bound for the chromatic number.

Of course, even with only 560 vertices this will not necessarily get you very far in a short amount of time. You can do tricks to help yourself with the time cost. Obviously you can start by throwing away vertices with degree lower than the bound you're hoping for. You can also partition the vertices of the graph into dense subgraphs, then try to bound the chromatic number of these subgraphs individually. Doing this using my RNSC (restricted neighbourhood search clustering) algorithm, which was originally used to find clusters in biological networks, helped a little bit with what Cook and Held were doing, but not too much.

I'm copy-pasting an abstract from a talk that Bill Cook gave this winter, which includes a link to their colouring page:

DATE: Tuesday, February 9

SPEAKER: Bill Cook (Georgia Tech)

TITLE: Computing the chromatic number of graphs

ABSTRACT: It can be very difficult in practice to optimally color a graph. For example, a set of randomly-generated test instances introduced by David Johnson in 1989 remain unsolved, the smallest example having only 125 vertices. We discuss the use of linear-programming methods to compute safe lower bounds on the chromatic number. Our methods do not depend on the floating-point accuracy of linear- programming software. This talk is based on joint work with Stephan Held (University of Bonn). Computational results and computer codes are freely available at site: http://code.google.com/p/exactcolors/

Improve this answer
$\endgroup$
1
  • $\begingroup$ By the way, you mention the Kneser graph. This is one graph class that can be used as a nasty example showing that the chromatic number is not necessarily upper-bounded by any function of the fractional chromatic number, meaning that in the worst case, the fractional chromatic number will give you a really lousy approximation. $\endgroup$
    – Andrew D. King
    Commented Sep 2, 2010 at 18:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .