Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871482 | Discrete Applied Mathematics | 2018 | 7 Pages |
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 V1,â¦,Vk in such a way that |V1|ââ{â|V|âkâ,â|V|âkâ} and âVi|â|Vjââ¤1 for each i,j=2,â¦,k. The color class V1 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 Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hanna FurmaÅczyk, Marek Kubale,