Coloring squares of graphs with mad constraints

Abstract: A proper vertex

k

-coloring of a graph

G = (V, E)

is an assignment

c : V o 1, 2, l d o t s, k

of colors to the vertices of the graph such that no two adjacent vertices are associated with the same color. The square

G^{2}

of a graph

G

is the graph defined by

V (G) = V (G^{2})

and

u v i n E (G^{2})

if and only if the distance between

u

and

v

is at most two. We denote by

c h i (G^{2})

the chromatic number of

G^{2}

, which is the least integer

k

such that a

k

-coloring of

G^{2}

exists. By definition, at least

D e l t a (G) + 1

colors are needed for this goal, where

D e l t a (G)

denotes the maximum degree of the graph

G

. In this paper, we prove that the square of every graph

G

with

e x t m a d (G) < 4

and

D e l t a (G) g e q s l a n t 8

is

(3 D e l t a (G) + 1)

-choosable and even correspondence-colorable. Furthermore, we show a family of

2

-degenerate graphs

G

with

e x t m a d (G) < 4

, arbitrarily large maximum degree, and

c h i (G^{2}) g e q s l a n t f r a c 5 D e l t a (G) 2

, improving the result of Kim and Park.

Recommendations

Cites Work

Cited In (7)

This page was built for publication: Coloring squares of graphs with mad constraints