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 | |