Tight Bounds on the Complexity of Semi-Equitable Coloring of Cubic and Subcubic Graphs
| Autor: | Furmańczyk, H., Kubale, M. |
|---|---|
| Rok vydání: | 2016 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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,\ldots,V_k$ in such a way that $|V_1| \notin \{\lceil |V|/k\rceil, \lfloor |V|/k \rfloor\}$ and $||V_i|-|V_j|| \leq 1$ for each $i,j=2,\ldots,k$. The color class $V_1$ is called non-equitable. In this note we consider the complexity of semi-equitable $k$-coloring, $k\geq 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 \geq 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 \geq n/3+\epsilon n$, and it is polynomially solvable if $s \leq n/3$. Comment: 11 pages, 2 figure |
| Databáze: | arXiv |
| Externí odkaz: |
|