Improved bounds on coloring of graphs

Abstract: Given a graph

G

with maximum degree

D e l t a g e 3

, we prove that the acyclic edge chromatic number

a^{'} (G)

of

G

is such that

a^{'} (G) l e l c e i l 9.62 (D e l t a - 1) c e i l

. Moreover we prove that:

a^{'} (G) l e l c e i l 6.42 (D e l t a - 1) c e i l

if

G

has girth

g g e 5,

;

a^{'} (G) l e l c e i l 5.77 (D e l t a - 1) c

if

G

has girth

g g e 7

;

a^{'} (G) l e l c 4.52 (D - 1) c

if

g g e 53

;

a^{'} (G) l e D + 2,

if

g g e l c e i l 25.84 D l o g D (1 + 4.1 / l o g D) c e i l

. We further prove that the acyclic (vertex) chromatic number

a (G)

of

G

is such that

a (G) l e l c 6.59 D e l t a^{4 / 3} + 3.3 D c

. We also prove that the star-chromatic number

c h i_{s} (G)

of

G

is such that

c h i_{s} (G) l e l c 4.34 D e l t a^{3 / 2} + 1.5 D c

. We finally prove that the

-frugal chromatic number

of

G

is such that

, where

and

are decreasing functions of

such that

and

. To obtain these results we use an improved version of the Lov'asz Local Lemma due to Bissacot, Fern'andez, Procacci and Scoppola cite{BFPS}.

Recommendations

Cites Work

Cited In (42)

This page was built for publication: Improved bounds on coloring of graphs