Home » Subject » Graph Theory » Coloring » Vertex coloring

Strong colorability

Importance: High ✭✭✭
Author(s): Aharoni, Ron
Alon, Noga
Haxell, Penny E.
Subject: Graph Theory
» Coloring
» » Vertex coloring
Keywords: strong coloring
Recomm. for undergrads: no
Posted by: berger
on: March 27th, 2007

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

Conjecture   If $ \Delta $ is the maximal degree of a graph $ G $, then $ G $ is strongly $ 2 \Delta $-colorable.

Haxell proved that if $ \Delta $ is the maximal degree of a graph $ G $, then $ G $ is strongly $ 3 \Delta - 1 $-colorable. She later proved that the strong chromatic number $ \chi_S $ is at most $ (2.75+\epsilon)\Delta $ for sufficiently large $ \Delta $ depending on $ \epsilon $. Aharoni, Berger, and Ziv proved the fractional relaxation.

add new comment

Recent progress

On November 19th, 2009 Andrew King says:

Haxell proved that $ (2.75 + \epsilon)\Delta $ is sufficient for sufficiently large $ \Delta $ depending on $ \epsilon $. (JGT, 2008)

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

reply

Problem Solved!

On July 24th, 2007 Anonymous says:

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

reply

only partly solved

On July 25th, 2007 Anonymous says:

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.

reply

That theorem has been proved

On September 3rd, 2007 Anonymous says:

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

reply

still only a partial solution

On September 3rd, 2007 mdevos says:

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 $ 2\Delta(G) $ if $ |V(G)| \le 6\Delta(G) $. 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 $ K $ so that every graph of maximum degree $ \Delta $ is strongly $ K \Delta $-colorable.. precisely the result which is sharpened by this conjecture.

reply

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.