2026-08-16T15:54:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5599 2024-03-06T10:36:38Z ddc:004 open_access

B-Chromatic Number: Beyond NP-Hardness Panolan, Fahad Philip, Geevarghese Saurabh, Saket b-chromatic number exact algorithm parameterized complexity 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)). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fahad Panolan and Geevarghese Philip and Saket Saurabh 2015 Is Part Of LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2015.389 urn:nbn:de:0030-drops-55997 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.389 eng https://creativecommons.org/licenses/by/3.0/legalcode