Outerstring Graphs are $\chi$-Bounded
From MaRDI portal
Publication:5244121
DOI10.1137/17M1157374zbMath1427.05149MaRDI QIDQ5244121
Bartosz Walczak, Alexandre Rok
Publication date: 20 November 2019
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
Coloring polygon visibility graphs and their generalizations ⋮ Quasiplanar graphs, string graphs, and the Erdős-Gallai problem ⋮ Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded ⋮ Coloring triangle-free L-graphs with \(O (\log \log n)\) colors ⋮ Coloring lines and Delaunay graphs with respect to boxes ⋮ Hasse diagrams with large chromatic number
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Triangle-free geometric intersection graphs with large chromatic number
- Triangle-free intersection graphs of line segments with large chromatic number
- Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
- Coloring intersection graphs of arc-connected sets in the plane
- Coloring intersection graphs of \(x\)-monotone curves in the plane
- Weakly transitive orientations, Hasse diagrams and string graphs
- On-line approach to off-line coloring problems on graphs with geometric representations
- How many ways can one draw a graph?
- New bounds on the maximum number of edges in \(k\)-quasi-planar graphs
- On the maximum number of edges in topological graphs with no four pairwise crossing edges
- On the chromatic number of multiple interval graphs and overlap graphs
- String graphs. II: Recognizing string graphs is NP-hard
- String graphs. I: The number of critical nonstring graphs is infinite
- String graphs requiring exponential representations
- Comparability graphs and intersection graphs
- Intersection graphs of curves in the plane
- The complexity of comparability graph recognition and coloring
- On the complexity of diagram testing
- Covering and coloring polygon-circle graphs
- Quasi-planar graphs have a linear number of edges
- Recognizing string graphs is decidable
- On the chromatic number of intersection graphs of convex sets in the plane
- Decidability of string graphs
- On bounding the chromatic number of L-graphs
- Applications of the crossing number
- Coloring triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors
- On grounded \(\llcorner\)-graphs and their relatives
- Coloring curves that cross a fixed curve
- A decomposition theorem for partially ordered sets
- On String Graph Limits and the Structure of a Typical String Graph
- A Separator Theorem for String Graphs and its Applications
- Coloring and Maximum Independent Set of Rectangles
- Research Problems in Discrete Geometry
- On a Coloring Problem.
- Coloring circle graphs
- A Ramsey-Type Result for Convex Sets
- Intersection Graphs of Rays and Grounded Segments
- Separators in region intersection graphs
- Circle graphs are quadratically χ‐bounded
- The Number of Edges in $k$-Quasi-planar Graphs
- Applications of a New Separator Theorem for String Graphs
- Near-Optimal Separators in String Graphs
- Topology of Thin Film RC Circuits
- The Number of Finite Topologies
- String graphs and incomparability graphs
- Refining the hierarchies of classes of geometric intersection graphs
- Recognizing string graphs in NP
- Colouring arcwise connected sets in the plane. I
