CISPA
Browse
s00453-024-01227-2.pdf (732.79 kB)

Conflict-Free Coloring: Graphs of Bounded Clique-Width and Intersection Graphs

Download (732.79 kB)
journal contribution
posted on 2024-05-22, 12:23 authored by Sriram Bhyravarapu, Tim A Hartmann, Hung P Hoang, Subrahmanyam Kalyanasundaram, I Vinod Reddy
A conflict-free coloring of a graph G is a (partial) coloring of its vertices such that every vertex u has a neighbor whose assigned color is unique in the neighborhood of u. There are two variants of this coloring, one defined using the open neighborhood and one using the closed neighborhood. For both variants, we study the problem of deciding whether the conflict-free coloring of a given graph G is at most a given number k. In this work, we investigate the relation of clique-width and minimum number of colors needed (for both variants) and show that these parameters do not bound one another. Moreover, we consider specific graph classes, particularly graphs of bounded clique-width and types of intersection graphs, such as distance hereditary graphs, interval graphs and unit square and disk graphs. We also consider Kneser graphs and split graphs. We give (often tight) upper and lower bounds and determine the complexity of the decision problem on these graph classes, which improve some of the results from the literature. Particularly, we settle the number of colors needed for an interval graph to be conflict-free colored under the open neighborhood model, which was posed as an open problem.

History

Primary Research Area

  • Algorithmic Foundations and Cryptography

Journal

Algorithmica: an international journal in computer science

Page Range

1-39

Publisher

Springer Nature

Open Access Type

  • Green

Sub Type

  • Article

BibTeX

@article{Bhyravarapu:Hartmann:Hoang:Kalyanasundaram:Vinod Reddy:2024, title = "Conflict-Free Coloring: Graphs of Bounded Clique-Width and Intersection Graphs", author = "Bhyravarapu, Sriram" AND "Hartmann, Tim A" AND "Hoang, Hung P" AND "Kalyanasundaram, Subrahmanyam" AND "Vinod Reddy, I", year = 2024, month = 4, journal = "Algorithmica: an international journal in computer science", pages = "1--39", publisher = "Springer Nature", issn = "0178-4617", doi = "10.1007/s00453-024-01227-2" }

Usage metrics

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC