We consider the complexity of semi-equitable k-coloring, k>3, of the vertices of a cubic or subcubic graph G. In particular, we show that, given a n-vertex subcubic graph G, 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, and it is polynomially solvable if s, n/3.
Authors
- Hanna Furmańczyk,
- prof. dr hab. inż. Marek Kubale link open in new tab
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.1016/j.dam.2017.12.002
- Category
- Publikacja w czasopiśmie
- Type
- artykuł w czasopiśmie wyróżnionym w JCR
- Language
- angielski
- Publication year
- 2018
