Tight Bounds on the Complexity of Semi-Equitable Coloring of Cubic and Subcubic Graphs

2016/06/20 by Furmańczyk, H., Kubale, M.
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1606.06333

Abstract

A k-coloring of a graph G=(V,E) is called semi-equitable if there exists a partition of its vertex set into independent subsets V₁,…,V_k in such a way that |V₁| ∉ \\lceil |V|/k\rceil, \lfloor |V|/k \rfloor\ and ||V_i|-|V_j|| ≤ 1 for each i,j=2,…,k. The color class V₁ is called non-equitable. In this note we consider the complexity of semi-equitable k-coloring, k≥ 4, of the vertices of a cubic or subcubic graph G. In particular, we show that, given a n-vertex subcubic graph G and constants ε> 0, k ≥ 4, it is NP-complete to obtain a semi-equitable k-coloring of G whose non-equitable color class is of size s if s ≥ n/3+εn, and it is polynomially solvable if s ≤ n/3.

Related

• Equitable coloring of corona products of cubic graphs is harder than\n ordinary coloring
• Equitable Colorings of l-Corona Products of Cubic Graphs
• Equitable colorings of complete multipartite graphs
• From semi-total to equitable total colorings
• Results and Problems on Equitable Coloring of Graphs