License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5599/
Go to the corresponding LIPIcs Volume Portal

Panolan, Fahad ; Philip, Geevarghese ; Saurabh, Saket

B-Chromatic Number: Beyond NP-Hardness

pdf-format:
36.pdf (0.5 MB)

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
Collection: 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Issue Date: 2015
Date of publication: 19.11.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI