Computer Science > Computational Complexity
[Submitted on 1 May 2019]
Title:Parameterized Complexity of Conflict-free Graph Coloring
View PDFAbstract:Given a graph G, a q-open neighborhood conflict-free coloring or q-ONCF-coloring is a vertex coloring $c:V(G) \rightarrow \{1,2,\ldots,q\}$ such that for each vertex $v \in V(G)$ there is a vertex in $N(v)$ that is uniquely colored from the rest of the vertices in $N(v)$. When we replace $N(v)$ by the closed neighborhood $N[v]$, then we call such a coloring a q-closed neighborhood conflict-free coloring or simply q-CNCF-coloring. In this paper, we study the NP-hard decision questions of whether for a constant q an input graph has a q-ONCF-coloring or a q-CNCF-coloring. We will study these two problems in the parameterized setting.
First of all, we study running time bounds on FPT-algorithms for these problems, when parameterized by treewidth. We improve the existing upper bounds, and also provide lower bounds on the running time under ETH and SETH.
Secondly, we study the kernelization complexity of both problems, using vertex cover as the parameter. We show that both $(q \geq 2)$-ONCF-coloring and $(q \geq 3)$-CNCF-coloring cannot have polynomial kernels when parameterized by the size of a vertex cover unless $NP \in coNP/poly$. However, we obtain a polynomial kernel for 2-CNCF-coloring parameterized by vertex cover.
We conclude with some combinatorial results. Denote $\chi_{ON}(G)$ and $\chi_{CN}(G)$ to be the minimum number of colors required to ONCF-color and CNCF-color G, respectively. Upper bounds on $\chi_{CN}(G)$ with respect to structural parameters like minimum vertex cover size, minimum feedback vertex set size and treewidth are known. To the best of our knowledge only an upper bound on $\chi_{ON}(G)$ with respect to minimum vertex cover size was known. We provide tight bounds for $\chi_{ON}(G)$ with respect to minimum vertex cover size. Also, we provide the first upper bounds on $\chi_{ON}(G)$ with respect to minimum feedback vertex set size and treewidth.
References & Citations
Bibliographic and Citation Tools
Bibliographic Explorer (What is the Explorer?)
Litmaps (What is Litmaps?)
scite Smart Citations (What are Smart Citations?)
Code, Data and Media Associated with this Article
alphaXiv (What is alphaXiv?)
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
DagsHub (What is DagsHub?)
Gotit.pub (What is GotitPub?)
Hugging Face (What is Huggingface?)
Papers with Code (What is Papers with Code?)
ScienceCast (What is ScienceCast?)
Demos
Recommenders and Search Tools
Influence Flower (What are Influence Flowers?)
Connected Papers (What is Connected Papers?)
CORE Recommender (What is CORE?)
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.