Equitable Coloring of Graphs with Intermediate Maximum Degree

Abstract: If the vertices of a graph

G

are colored with

k

colors such that no adjacent vertices receive the same color and the sizes of any two color classes differ by at most one, then

G

is said to be equitably

k

-colorable. Let

| G |

denote the number of vertices of

G

and

D e l t a = D e l t a (G)

the maximum degree of a vertex in

G

. We prove that a graph

G

of order at least 6 is equitably

D e l t a

-colorable if

G

satisfies

(| G | + 1) / 3 l e q D e l t a < | G | / 2

and none of its components is a

K_{D e l t a + 1}

.

This page was built for publication: Equitable Coloring of Graphs with Intermediate Maximum Degree