Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2015.389
URN: urn:nbn:de:0030-drops-55997
URL: https://drops.dagstuhl.de/opus/volltexte/2015/5599/
Panolan, Fahad ; Philip, Geevarghese ; Saurabh, Saket
B-Chromatic Number: Beyond NP-Hardness
| pdf-format: |
|
Abstract
The b-chromatic number of a graph G, chi_b(G), is the largest integer k such that G has a k-vertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other color classes. In the B-Chromatic Number problem, the objective is to decide whether chi_b(G) >= k. Testing whether chi_b(G)=Delta(G)+1, where Delta(G) is the maximum degree of a graph, itself is NP-complete even for connected bipartite graphs (Kratochvil, Tuza and Voigt, WG 2002). In this paper we study B-Chromatic Number in the realm of parameterized complexity and exact exponential time algorithms. We show that B-Chromatic Number is W[1]-hard when parameterized by k, resolving the open question posed by Havet and Sampaio (Algorithmica 2013). When k=Delta(G)+1, we design an algorithm for B-Chromatic Number running in time 2^{O(k^2 * log(k))}*n^{O(1)}. Finally, we show that B-Chromatic Number for an n-vertex graph can be solved in time O(3^n * n^{4} * log(n)).
BibTeX - Entry
@InProceedings{panolan_et_al:LIPIcs:2015:5599,
author = {Fahad Panolan and Geevarghese Philip and Saket Saurabh},
title = {{B-Chromatic Number: Beyond NP-Hardness}},
booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
pages = {389--401},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-92-7},
ISSN = {1868-8969},
year = {2015},
volume = {43},
editor = {Thore Husfeldt and Iyad Kanj},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5599},
URN = {urn:nbn:de:0030-drops-55997},
doi = {10.4230/LIPIcs.IPEC.2015.389},
annote = {Keywords: b-chromatic number, exact algorithm, parameterized complexity}
}
| Keywords: | b-chromatic number, exact algorithm, parameterized complexity | |
| Seminar: | 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) | |
| Issue date: | 2015 | |
| Date of publication: | 19.11.2015 |
