Vis enkel innførsel

dc.contributor.authorPanolan, Fahad
dc.contributor.authorPhilip, Geevarghese
dc.contributor.authorSaurabh, Saket
dc.description.abstractThe 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)).en_US
dc.publisherDagstuhl Publishingen_US
dc.rightsAttribution CC BY 3.0eng
dc.subjectb-chromatic numbereng
dc.subjectexact algorithmeng
dc.subjectParameterized complexityeng
dc.titleB-chromatic number: Beyond NP-hardnessen_US
dc.typePeer reviewed
dc.typeJournal article
dc.rights.holderCopyright Fahad Panolan, Geevarghese Philip, and Saket Saurabhen_US
dc.source.journalLeibniz International Proceedings in Informatics
dc.subject.nsiVDP::Matematikk og Naturvitenskap: 400en_US
dc.identifier.citationLeibniz International Proceedings in Informatics 2015, 43:389-401

Tilhørende fil(er)


Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel

Attribution CC BY 3.0
Med mindre annet er angitt, så er denne innførselen lisensiert som Attribution CC BY 3.0