We consider conflict-free colorings of graph neighborhoods: Each vertex of the graph must be assigned a color so that for each vertex v there is at least one color appearing exactly once in the neighborhood of v. The goal is to minimize the number of used colors. We consider both the case of closed neighborhoods, when the neighborhood of a node includes the node itself, and the case of open neighborhoods when a node does not belong to its neighborhood. In this paper, we study complexity aspects of the problem. We show that the problem of conflict-free coloring of closed neighborhoods is NP-complete. Moreover, we give non-approximability results for the conflict-free coloring of open neighborhoods. From a positive point of view, both problems become tractable if parameterized by the vertex cover number or the neighborhood diversity number of the graph. We present simple algorithms which improve on existing results.

Complexity of conflict-free colorings of graphs

GARGANO, Luisa;RESCIGNO, Adele Anna
2015-01-01

Abstract

We consider conflict-free colorings of graph neighborhoods: Each vertex of the graph must be assigned a color so that for each vertex v there is at least one color appearing exactly once in the neighborhood of v. The goal is to minimize the number of used colors. We consider both the case of closed neighborhoods, when the neighborhood of a node includes the node itself, and the case of open neighborhoods when a node does not belong to its neighborhood. In this paper, we study complexity aspects of the problem. We show that the problem of conflict-free coloring of closed neighborhoods is NP-complete. Moreover, we give non-approximability results for the conflict-free coloring of open neighborhoods. From a positive point of view, both problems become tractable if parameterized by the vertex cover number or the neighborhood diversity number of the graph. We present simple algorithms which improve on existing results.
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0304397514009463-main.pdf

accesso aperto

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Creative commons
Dimensione 413.66 kB
Formato Adobe PDF
413.66 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/4678770
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 41
  • ???jsp.display-item.citation.isi??? 29
social impact