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

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_1,\dots ,V_k$ in such a way that $|V_1|\notin \{\lceil |V|/k\rceil ,\lfloor |V|/k\rfloor \}$ and $||V_i|-|V_j||\le 1$ for each $i,j=2,\dots ,k$. The color class $V_1$ is called non-equitable. In this note we consider the complexity of semi-equitable $k$-coloring, $k\ge 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 $\epsilon >0$, $k\ge 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\ge n/3+\epsilon n$, and it is polynomially solvable if $s\le n/3$.

11 pages, 2 figure

Cited by in corpus (2)

• Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs
• Equitable Colorings of $l$-Corona Products of Cubic Graphs