Coloring Graphs with Dense Neighborhoods

Abstract: It is shown that any graph with maximum degree

D e l t a

in which the average degree of the induced subgraph on the set of all neighbors of any vertex exceeds

f r a c 6 k^{2} 6 k^{2} + 1 D e l t a + k + 6

is either

(D e l t a - k)

-colorable or contains a clique on more than

D e l t a - 2 k

vertices. In the

k = 1

case we improve the bound on the average degree to

f r a c 23 D e l t a + 4

and the bound on the clique number to

D e l t a - 1

. As corollaries, we show that every graph satisfies

c h i l e q m a x s e t o m e g a, D e l t a - 1, 4 a l p h a

and every graph satisfies

c h i l e q m a x s e t o m e g a, D e l t a - 1, c e i l f r a c 15 + s q r t 48 n + 73 4

.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Coloring Graphs with Dense Neighborhoods