On the parameterized complexity of b-chromatic number

作者：

Highlights：

• We show that b-Chromatic Number is W[1]-hard when parameterized by the b-chromatic number, k.

• When k=Δ(G)+1, an algorithm of running in 2O(k2log⁡k)nO(1) is provided.

• An O(3nn4log⁡n) time algorithm on an n-vertex graph is provided.

摘要

•We show that b-Chromatic Number is W[1]-hard when parameterized by the b-chromatic number, k.•When k=Δ(G)+1, an algorithm of running in 2O(k2log⁡k)nO(1) is provided.•An O(3nn4log⁡n) time algorithm on an n-vertex graph is provided.

论文关键词：b-Chromatic number,Exact algorithm,Parameterized complexity

论文评审过程：Received 20 September 2015, Revised 29 September 2016, Accepted 30 September 2016, Available online 11 October 2016, Version of Record 14 November 2016.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.09.012