A new vertex coloring heuristic and corresponding chromatic number
Preprint
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 {\rm 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, \ldots, C_k$ such that $(i)$ for any two colors $i$ and $j$ with $1\leq i< j \leq k$, any vertex of color $j$ is adjacent to a vertex of color $i$, $(ii)$ there exists a set $\{u_1, \ldots, u_k\}$ of vertices of $G$ such that $u_j\in C_j$ for any $j\in \{1, \ldots, k\}$ and $u_k$ is adjacent to $u_j$ for each $1\leq j \leq k$ with $j\not= k$, and $(iii)$ for each $i$ and $j$ with $i\not= 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\geq 1}$ such that $\min \{\Gamma(G_n), b(G_n)\} \rightarrow \infty$ but $z(G_n)\leq 3$ for each $n$. For each positive integer $t$ we construct a family of finitely many colored graphs ${\mathcal{D}}_t$ satisfying the property that if $z(G)\geq t$ for a graph $G$ then $G$ contains an element from ${\mathcal{D}}_t$ as a colored subgraph. This provides an algorithmic method for proving numeric upper bounds for $z(G)$.
Keywords
All Related Versions
- Version 1, 2020-11-14, ArXiv
- Published version: Algorithmica, 82 (9), 2395.
This publication has 11 references indexed in Scilit:
- Complexity of Grundy coloring and its variantsDiscrete Applied Mathematics, 2018
- The b-chromatic number and related topics—A surveyDiscrete Applied Mathematics, 2018
- A characterization of b-chromatic and partial Grundy numbers by induced subgraphsDiscrete Mathematics, 2016
- On the Grundy and b-Chromatic Numbers of a GraphAlgorithmica, 2011
- A survey on vertex coloring problemsInternational Transactions in Operational Research, 2009
- Results on the Grundy chromatic number of graphsDiscrete Mathematics, 2006
- Linear degree extractors and the inapproximability of max clique and chromatic number2006
- The greedy algorithm is optimal for on-line edge coloringInformation Processing Letters, 1992
- An Analysis of a Good Algorithm for the Subtree Problem, CorrectedSIAM Journal on Computing, 1989
- On‐line and first fit colorings of graphsJournal of Graph Theory, 1988