Home » Subject » Graph Theory » Coloring » Vertex coloring
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.

5 comments

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options