A new vertex coloring heuristic and corresponding chromatic number

11/14/2020
by   Manouchehr Zaker, et al.
0

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 C_1, …, C_k 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 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≥ 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 𝒟_t satisfying the property that if z(G)≥ t for a graph G then G contains an element from 𝒟_t as a colored subgraph. This provides an algorithmic method for proving numeric upper bounds for z(G).

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset