A New Vertex Coloring Heuristic and Corresponding Chromatic Number
- PDF / 515,403 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 77 Downloads / 214 Views
A New Vertex Coloring Heuristic and Corresponding Chromatic Number Manouchehr Zaker1 Received: 5 September 2018 / Accepted: 5 February 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
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 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 C1 , . . . , Ck such that (i) for any two colors i and j with 1 ≤ i < j ≤ k, any vertex of color j is adjacent to a vertex of color i, (ii) there exists a set {u 1 , . . . , u k } of vertices of G such that u j ∈ C j for any j ∈ {1, . . . , k} and u k is adjacent to u j for each 1 ≤ j ≤ k with j = k, and (iii) for each i and j with i = j, the vertex u j has a neighbor in Ci . 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≥1 such that min{(G n ), b(G n )} → ∞ but z(G n ) ≤ 3 for each n. For each positive integer t we construct a family of finitely many colored graphs Dt satisfying the property that if z(G) ≥ t for a graph G then G contains an element from Dt as a colored subgraph. This provides an algorithmic method for proving numeric upper bounds for z(G). Keywords Graph coloring · Coloring algorithms · Greedy coloring · Grundy coloring · Color-dominating coloring Mathematics Subject Classification 05C15 · 68W05 · 05C85
B 1
Manouchehr Zaker [email protected] Department of Mathematics, Institute for Advanced Studies in Basic Sciences, Zanjan 45137-66731, Iran
123
Algorithmica
1 Introduction All graphs in this paper are simple and undirected. Let G be a graph with the vertex set V (G). By a proper vertex coloring of G we mean any function C : V (G) → N such that for each adjacent vertices u and v, C(u) = C(v). In this paper by vertex colorings, we always mean proper vertex colorings of graphs. Denote by χ (G) the minimum number of colors used in any proper vertex coloring of a graph G. A very strong result proved by Zuckerman [17] asserts that for every arbitrary and fixed > 0 if there exists a polynomial time algorithm A such that for every graph G on n vertices, A(G)/χ (G) ≤ n 1− then N P ⊆ P, where A(G) denotes the number of colors used by the algorithm A to color the graph G. This in particular proves that it is a har
Data Loading...
