A new vertex coloring heuristic and corresponding chromatic number

DOI10.1007/S00453-020-00689-4MaRDI QIDQ2196603zbMATH OpenOpenAlexFDO

Publication date 3 September 2020

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.07295

color-dominating coloring coloring algorithms graph coloring greedy coloring Grundy coloring

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Nonnumerical algorithms (68W05)

Abstract: One method to obtain a proper vertex coloring of graphs using a reasonable number of colors is to start from any arbitrary proper coloring and then repeat some local re-coloring techniques to reduce the number of color classes. The Grundy (First-Fit) coloring and color-dominating colorings of graphs are two well-known such techniques. The color-dominating colorings are also known and commonly referred as { m b}-colorings. But these two topics have been studied separately in graph theory. We introduce a new coloring procedure which combines the strategies of these two techniques and satisfies an additional property. We first prove that the vertices of every graph

G

can be effectively colored using color classes say

C_{1}, l d o t s, C_{k}

such that

(i)

for any two colors

i

and

j

with

1 l e q i < j l e q k

, any vertex of color

j

is adjacent to a vertex of color

i

,

(i i)

there exists a set

u_{1}, l d o t s, u_{k}

of vertices of

G

such that

u_{j} i n C_{j}

for any

j i n 1, l d o t s, k

and

u_{k}

is adjacent to

u_{j}

for each

1 l e q j l e q k

with

j o t = k

, and

(i i i)

for each

i

and

j

with

i o t = j

, the vertex

u_{j}

has a neighbor in

C_{i}

. This provides a new vertex coloring heuristic which improves both Grundy and color-dominating colorings. Denote by

z (G)

the maximum number of colors used in any proper vertex coloring satisfying the above properties. The

z (G)

quantifies the worst-case behavior of the heuristic. We prove the existence of

{G_{n}}_{n g e q 1}

such that

m i n G a m m a (G_{n}), b (G_{n}) i g h t a r r o w i n f t y

but

z (G_{n}) l e q 3

for each

n

. For each positive integer

t

we construct a family of finitely many colored graphs

{m a t h c a l D}_{t}

satisfying the property that if

z (G) g e q t

for a graph

G

then

G

contains an element from

{m a t h c a l D}_{t}

as a colored subgraph. This provides an algorithmic method for proving numeric upper bounds for

z (G)

.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: A new vertex coloring heuristic and corresponding chromatic number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2196603)