Jaffke, Lars ;
Lima, Paloma T.
A Complexity Dichotomy for Critical Values of the bChromatic Number of Graphs
Abstract
A bcoloring of a graph G is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The bColoring problem asks whether a graph G has a bcoloring with k colors. The bchromatic number of a graph G, denoted by chi_b(G), is the maximum number k such that G admits a bcoloring with k colors. We consider the complexity of the bColoring problem, whenever the value of k is close to one of two upper bounds on chi_b(G): The maximum degree Delta(G) plus one, and the mdegree, denoted by m(G), which is defined as the maximum number i such that G has i vertices of degree at least i1. We obtain a dichotomy result for all fixed k in N when k is close to one of the two above mentioned upper bounds. Concretely, we show that if k in {Delta(G) + 1  p, m(G)  p}, the problem is polynomialtime solvable whenever p in {0, 1} and, even when k = 3, it is NPcomplete whenever p >= 2. We furthermore consider parameterizations of the bColoring problem that involve the maximum degree Delta(G) of the input graph G and give two FPTalgorithms. First, we show that deciding whether a graph G has a bcoloring with m(G) colors is FPT parameterized by Delta(G). Second, we show that bColoring{} is FPT parameterized by Delta(G) + l_k(G), where l_k(G) denotes the number of vertices of degree at least k.
BibTeX  Entry
@InProceedings{jaffke_et_al:LIPIcs:2019:10978,
author = {Lars Jaffke and Paloma T. Lima},
title = {{A Complexity Dichotomy for Critical Values of the bChromatic Number of Graphs}},
booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
pages = {34:134:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771177},
ISSN = {18688969},
year = {2019},
volume = {138},
editor = {Peter Rossmanith and Pinar Heggernes and JoostPieter Katoen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10978},
URN = {urn:nbn:de:0030drops109784},
doi = {10.4230/LIPIcs.MFCS.2019.34},
annote = {Keywords: bColoring, bChromatic Number}
}
20.08.2019
Keywords: 

bColoring, bChromatic Number 
Seminar: 

44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Issue date: 

2019 
Date of publication: 

20.08.2019 