## Abstract

Given a graph G, a q-open neighborhood conflict-free coloring or q-ONCF-coloring is a vertex coloring c: V(G) → { 1, 2, …, q} such that for each vertex v∈ 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≥ 2) -ONCF-coloring and (q≥ 3) -CNCF-coloring cannot have polynomial kernels when parameterized by the size of a vertex cover unless NP⊆ coNP/poly. On the other hand, we obtain a polynomial kernel for 2-CNCF-coloring parameterized by vertex cover. We conclude the study with some combinatorial results. Denote χ_{ON}(G) and χ_{CN}(G) to be the minimum number of colors required to ONCF-color and CNCF-color G, respectively. Upper bounds on χ_{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 χ_{ON}(G) with respect to minimum vertex cover size was known. We provide tight bounds for χ_{ON}(G) with respect to minimum vertex cover size. Also, we provide the first upper bounds on χ_{ON}(G) with respect to minimum feedback vertex set size and treewidth.

Original language | English |
---|---|

Title of host publication | Algorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings |

Editors | Zachary Friggstad, Mohammad R. Salavatipour, Jörg-Rüdiger Sack |

Place of Publication | Cham |

Publisher | Springer |

Pages | 168-180 |

Number of pages | 13 |

ISBN (Electronic) | 978-3-030-24766-9 |

ISBN (Print) | 978-3-030-24765-2 |

DOIs | |

Publication status | Published - 12 Jul 2019 |

Event | 16th International Symposium on Algorithms and Data Structures, WADS 2019 - Edmonton, Canada Duration: 5 Aug 2019 → 7 Aug 2019 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 11646 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 16th International Symposium on Algorithms and Data Structures, WADS 2019 |
---|---|

Country/Territory | Canada |

City | Edmonton |

Period | 5/08/19 → 7/08/19 |

## Keywords

- Combinatorial bounds
- Conflict-free coloring
- Fixed-parameter tractability
- Kernelization