Abstract
In this paper we consider the complexity of semi-equitable k-coloring of the vertices of a cubic or subcubic graph. We show that, given n-vertex subcubic graph G, a semi-equitable k-coloring of G is NP-hard if s >= 7n/20 and polynomially solvable if s <= 7n/21, where s is the size of maximum color class of the coloring.
Authors (2)
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Conference activity
- Type:
- publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
- Title of issue:
- Bordeaux Graph Workshop strony 138 - 140
- Language:
- English
- Publication year:
- 2016
- Bibliographic description:
- Kubale M., Furmańczyk H.: Sharp bounds for the complexity of semi-equitable coloring of cubic and subcubic graphs// Bordeaux Graph Workshop/ Bordeaux: Eiseirb-Matmeca & LaBRI, 2016, s.138-140
- Verified by:
- Gdańsk University of Technology
seen 105 times