Open Problem Garden - Strong colorability - Comments

Recent progress (re: Strong colorability)

Andrew King — Thu, 19 Nov 2009 18:36:53 +0100

Haxell proved that is sufficient for sufficiently large depending on . (JGT, 2008)

Aharoni, Berger, and Ziv proved the fractional relaxation, i.e. that with partition cliques of size we have a fractional colouring. (Combinatorica, 2007)

still only a partial solution (re: Strong colorability)

mdevos — Mon, 03 Sep 2007 22:45:00 +0200

Once again, the paper cited offers only a partial solution. Quoting from the paper, "From Theorem 1.1, we conclude that the strong chromatic number can be bounded by if . This result should not be compared with the more complete and difficult result of Alon." Here, the difficult result of Alon is the theorem that there exists a fixed constant so that every graph of maximum degree is strongly -colorable.. precisely the result which is sharpened by this conjecture.

That theorem has been proved (re: Strong colorability)

Anonymous — Mon, 03 Sep 2007 22:27:50 +0200

That theorem has been proved in an even older paper by another set of authors.

After a quick search I found that paper at http://abel.math.umu.se/~klasm/Uppsatser/factor.pdf

only partly solved (re: Strong colorability)

Anonymous — Wed, 25 Jul 2007 00:26:12 +0200

The paper cited (available at http://orion.math.iastate.edu/axenovic/Papers/Martin_Strong.pdf) only resolves the above conjecture for graphs G which have maximum degree at least |V(G)|/6.

Problem Solved! (re: Strong colorability)

Anonymous — Tue, 24 Jul 2007 11:24:09 +0200

See "On the Strong Chromatic Number of Graphs" by Maria Axenovich and Ryan Martin (2006)

Strong colorability

berger — Tue, 27 Mar 2007 13:53:26 +0200

Author(s): Aharoni; Alon; Haxell

Subject: Graph Theory » Coloring » Vertex coloring

Let be a positive integer. We say that a graph is strongly -colorable if for every partition of the vertices to sets of size at most there is a proper -coloring of in which the vertices in each set of the partition have distinct colors.

Conjecture If is the maximal degree of a graph , then is strongly -colorable.