dc.contributor.author Panolan, Fahad dc.contributor.author Philip, Geevarghese dc.contributor.author Saurabh, Saket dc.date.accessioned 2016-05-27T11:39:24Z dc.date.available 2016-05-27T11:39:24Z dc.date.issued 2015 dc.identifier.isbn 978-3-939897-92-7 dc.identifier.issn 1868-8969 en_US dc.identifier.uri https://hdl.handle.net/1956/12026 dc.description.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)). en_US dc.language.iso eng eng dc.publisher Dagstuhl Publishing en_US dc.rights Attribution CC BY 3.0 eng dc.rights.uri http://creativecommons.org/licenses/by/3.0 eng dc.subject b-chromatic number eng dc.subject exact algorithm eng dc.subject Parameterized complexity eng dc.title B-chromatic number: Beyond NP-hardness en_US dc.type Peer reviewed dc.type Journal article dc.date.updated 2016-03-30T10:15:27Z dc.description.version publishedVersion en_US dc.rights.holder Copyright Fahad Panolan, Geevarghese Philip, and Saket Saurabh en_US dc.identifier.doi https://doi.org/10.4230/lipics.ipec.2015.389 dc.identifier.cristin 1344935 dc.source.journal Leibniz International Proceedings in Informatics dc.source.pagenumber 389-401 dc.subject.nsi VDP::Matematikk og Naturvitenskap: 400 en_US dc.identifier.citation Leibniz International Proceedings in Informatics 2015, 43:389-401 dc.source.volume 43
﻿

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

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