Sharp bounds for the complexity of semi-equitable coloring of cubic and subcubic graphs

Marek Kubale; Hanna Furmańczyk

Sharp bounds for the complexity of semi-equitable coloring of cubic and subcubic graphs

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)

Marek Kubale prof. dr hab. inż.
Hanna Furmańczyk
- Instytut Informatyki UG .

Cite as

Full text

full text is not available in portal

full content of the article see on external site open in new tab

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