Conflict-free coloring of string graphs

DOI10.1007/s00454-020-00179-yzbMath1462.05142arXiv1712.04524OpenAlexW3005028703MaRDI QIDQ2022631

Alexandre Rok, Chaya Keller, Shakhar Smorodinsky

Publication date: 29 April 2021

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1712.04524

zbMATH Keywords

string graphsconflict-free coloringcircle graphs\(k\)-CF coloringgrounded L-shapes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Intersection graphs of L-shapes and segments in the plane
• Asymmetric coloring games on incomparability graphs
• On the number of anchored rectangle packings for a planar point set
• Triangle-free intersection graphs of line segments with large chromatic number
• Coloring intersection graphs of arc-connected sets in the plane
• Complexity of conflict-free colorings of graphs
• Coloring intersection graphs of \(x\)-monotone curves in the plane
• On-line approach to off-line coloring problems on graphs with geometric representations
• Decomposition of multiple coverings into many parts
• On the chromatic number of multiple interval graphs and overlap graphs
• String graphs requiring exponential representations
• Intersection graphs of curves in the plane
• Colouring relatives of intervals on the plane. II: Intervals and rays in two directions
• Covering and coloring polygon-circle graphs
• Coloring relatives of intervals on the plane. I: Chromatic number versus girth
• Induced subgraphs of graphs with large chromatic number. XI. Orientations
• Recognizing string graphs is decidable
• On bounding the chromatic number of L-graphs
• Conflict-free coloring of intersection graphs of geometric objects
• Coloring triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors
• Conflict-free coloring of points and simple regions in the plane
• Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set
• A Separator Theorem for String Graphs and its Applications
• On The Chromatic Number of Geometric Hypergraphs
• Conflict-Free Colourings of Graphs and Hypergraphs
• Conflict-Free Coloring Made Stronger
• CONFLICT-FREE COLORINGS OF SHALLOW DISCS
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Three Colors Suffice: Conflict-Free Coloring of Planar Graphs
• Coloring curves that cross a fixed curve
• Outerstring graphs are χ-bounded
• Über wesentlich unplättbare Kurven im dreidimensionalen Raume
• Planar Graphs as VPG-Graphs
• Online conflict-free coloring for halfplanes, congruent disks, and axis-parallel rectangles
• Coloring intersection hypergraphs of pseudo-disks
• Decomposing Coverings and the Planar Sensor Cover Problem
• Conflict-Free Coloring and its Applications
• Applications of a New Separator Theorem for String Graphs
• Near-Optimal Separators in String Graphs
• Conflict-Free Colouring of Graphs
• Online Conflict‐Free Coloring for Intervals
• Toward a theory of crossing numbers
• String graphs and incomparability graphs
• Recognizing string graphs in NP
• Indecomposable Coverings
• Colouring arcwise connected sets in the plane. I

This page was built for publication: Conflict-free coloring of string graphs