Conflict-free coloring of graphs
From MaRDI portal
Publication:4556952
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph minors (05C83)
Abstract: A conflict-free k-coloring of a graph assigns one of k different colors to some of the vertices such that, for every vertex v, there is a color that is assigned to exactly one vertex among v and v's neighbors. Such colorings have applications in wireless networking, robotics, and geometry, and are well-studied in graph theory. Here we study the natural problem of the conflict-free chromatic number chi_CF(G) (the smallest k for which conflict-free k-colorings exist). We provide results both for closed neighborhoods N[v], for which a vertex v is a member of its neighborhood, and for open neighborhoods N(v), for which vertex v is not a member of its neighborhood. For closed neighborhoods, we prove the conflict-free variant of the famous Hadwiger Conjecture: If an arbitrary graph G does not contain K_{k+1} as a minor, then chi_CF(G) <= k. For planar graphs, we obtain a tight worst-case bound: three colors are sometimes necessary and always sufficient. We also give a complete characterization of the computational complexity of conflict-free coloring. Deciding whether chi_CF(G)<= 1 is NP-complete for planar graphs G, but polynomial for outerplanar graphs. Furthermore, deciding whether chi_CF(G)<= 2 is NP-complete for planar graphs G, but always true for outerplanar graphs. For the bicriteria problem of minimizing the number of colored vertices subject to a given bound k on the number of colors, we give a full algorithmic characterization in terms of complexity and approximation for outerplanar and planar graphs. For open neighborhoods, we show that every planar bipartite graph has a conflict-free coloring with at most four colors; on the other hand, we prove that for k in {1,2,3}, it is NP-complete to decide whether a planar bipartite graph has a conflict-free k-coloring. Moreover, we establish that any general} planar graph has a conflict-free coloring with at most eight colors.
Recommendations
Cites work
- scientific article; zbMATH DE number 5506190 (Why is no real title available?)
- scientific article; zbMATH DE number 3102312 (Why is no real title available?)
- A linear algorithm for the domination number of a series-parallel graph
- Approximation algorithms for NP-complete problems on planar graphs
- Complexity of conflict-free colorings of graphs
- Conflict-Free Colorings of Rectangles Ranges
- Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
- Conflict-free coloring for rectangle ranges using \(O(n ^{.382})\) colors
- Conflict-free coloring made stronger
- Conflict-free coloring of points and simple regions in the plane
- Conflict-free coloring of unit disks
- Conflict-free colouring of graphs
- Conflict-free colourings of graphs and hypergraphs
- Every planar map is four colorable. I: Discharging
- Every planar map is four colorable. II: Reducibility
- Exact and FPT algorithms for MAX-conflict free coloring in hypergraphs
- Graph unique-maximum and conflict-free colorings
- Minimum-weight triangulation is NP-hard
- Online Conflict‐Free Coloring for Intervals
- Online conflict-free colouring for hypergraphs
- Polynomial-time data reduction for dominating set
- Strong conflict-free coloring for intervals
- The four-colour theorem
- The potential to improve the choice, list conflict-free coloring for geometric hypergraphs
- Three colors suffice: conflict-free coloring of planar graphs
- Tight bounds for conflict-free chromatic guarding of orthogonal art galleries
Cited in
(30)- Conflict-free coloring bounds on open neighborhoods
- Structural parameterization for minimum conflict-free colouring
- Remarks on proper conflict-free colorings of graphs
- Conflict-free colouring of graphs
- Single‐conflict colouring
- scientific article; zbMATH DE number 6613348 (Why is no real title available?)
- Odd coloring of sparse graphs and planar graphs
- Conflict-free coloring: graphs of bounded clique-width and intersection graphs
- Three colors suffice: conflict-free coloring of planar graphs
- Conflict-free coloring of string graphs
- Improper odd coloring of IC-planar graphs
- Parameterized Complexity of Conflict-Free Graph Coloring
- Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth
- A note on the conflict-free chromatic index
- Colouring a dominating set without conflicts: \(q\)-subset square colouring
- On odd colorings of planar graphs
- A short note on conflict‐free coloring on closed neighborhoods of bounded degree graphs
- A tight bound for conflict-free coloring in terms of distance to cluster
- Conflict free colorings of nonuniform systems of infinite sets
- Theory and application of conflict resolution with hybrid preference in colored graphs
- Complexity of conflict-free colorings of graphs
- Conflict-free coloring of unit disks
- Proper conflict-free coloring of sparse graphs
- Conflict-free coloring of intersection graphs
- Conflict-free coloring of intersection graphs
- Parameterized algorithms for conflict-free colorings of graphs
- Non-monochromatic and conflict-free colorings on tree spaces and planar network spaces
- A short note on open-neighborhood conflict-free colorings of graphs
- Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods
- Conflict-free coloring: graphs of bounded clique width and intersection graphs
This page was built for publication: Conflict-free coloring of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4556952)
