Lower bounds for chromatic number of a graph - MathOverflow

Lower bounds for chromatic number of a graph

2010-07-29T17:30:42Z

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?

Answer by Matthew Kahle for Lower bounds for chromatic number of a graph

2010-07-29T18:48:36Z

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.

Answer by Nathann Cohen for Lower bounds for chromatic number of a graph

2010-07-30T02:22:27Z

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

Answer by miforbes for Lower bounds for chromatic number of a graph

2010-07-30T08:51:16Z

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.

Answer by Bobby Kleinberg for Lower bounds for chromatic number of a graph

2010-07-30T11:09:03Z

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

Answer by Marco Chiarandini for Lower bounds for chromatic number of a graph

2010-07-30T16:20:02Z

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

Answer by Andrew D. King for Lower bounds for chromatic number of a graph

2010-09-02T18:17:01Z

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/