Triangle-free intersection graphs of line segments with large chromatic number

DOI10.1016/j.jctb.2013.11.001zbMath1300.05106arXiv1209.1595OpenAlexW3101282841MaRDI QIDQ401487

Bartosz Walczak, Tomasz Krawczyk, Jakub Kozik, Michał Lasoń, Arkadiusz Pawlik, Piotr Micek, William T. jun. Trotter

Publication date: 27 August 2014

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

intersection graph chromatic number triangle-free line segments

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items (52)

Disjointness graphs of segments in the space ⋮ Cops and robbers on intersection graphs ⋮ The chromatic number of graphs with no induced subdivision of $K_4$ ⋮ Triangle-free geometric intersection graphs with large chromatic number ⋮ Coloring curves that cross a fixed curve ⋮ Coloring polygon visibility graphs and their generalizations ⋮ Triangle‐free graphs with large chromatic number and no induced wheel ⋮ The chromatic number of {ISK4, diamond, bowtie}‐free graphs ⋮ Some remarks on graphs with no induced subdivision of $K_4$ ⋮ Quasiplanar graphs, string graphs, and the Erdős-Gallai problem ⋮ Amalgams and χ-Boundedness ⋮ Disjointness graphs of short polygonal chains ⋮ Burling graphs revisited. II: Structure ⋮ Burling graphs revisited. III: Applications to $\chi $-boundedness ⋮ Chromatic number of ISK4-free graphs ⋮ Ramsey properties of semilinear graphs ⋮ The thickness of fan-planar graphs is at most three ⋮ Coloring triangle-free L-graphs with $O (\log \log n)$ colors ⋮ Graphs of large chromatic number ⋮ Coloring lines and Delaunay graphs with respect to boxes ⋮ Induced subgraphs of graphs with large chromatic number. VI. Banana trees ⋮ Decomposition of Multiple Packings with Subquadratic Union Complexity ⋮ Graph theory. Abstracts from the workshop held January 2--8, 2022 ⋮ Coloring Hasse diagrams and disjointness graphs of curves ⋮ On graphs with no induced subdivision of $K_4$ ⋮ Burling graphs revisited. I: New characterizations ⋮ Coloring intersection graphs of arc-connected sets in the plane ⋮ Refining the hierarchies of classes of geometric intersection graphs ⋮ Excluding cycles with a fixed number of chords ⋮ On the speed of algebraically defined graph classes ⋮ Coloring intersection graphs of $x$-monotone curves in the plane ⋮ Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors ⋮ Box and Segment Intersection Graphs with Large Girth and Chromatic Number ⋮ Coloring triangle-free rectangle overlap graphs with $O(\log \log n)$ colors ⋮ Triangle-free geometric intersection graphs with no large independent sets ⋮ Conflict-free coloring of string graphs ⋮ Unnamed Item ⋮ Burling graphs, chromatic number, and orthogonal tree-decompositions ⋮ On-line approach to off-line coloring problems on graphs with geometric representations ⋮ Coloring non-crossing strings ⋮ Planar point sets determine many pairwise crossing segments ⋮ Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings ⋮ Refining the hierarchies of classes of geometric intersection graphs ⋮ Pure pairs. II: Excluding all subdivisions of a graph ⋮ On the chromatic number of disjointness graphs of curves ⋮ Outerstring Graphs are $\chi$-Bounded ⋮ Burling graphs, chromatic number, and orthogonal tree-decompositions ⋮ Quasi-planar Graphs ⋮ Hasse diagrams with large chromatic number ⋮ From $\chi$- to $\chi_p$-bounded classes ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure ⋮ Restricted frame graphs and a conjecture of Scott

Cites Work

This page was built for publication: Triangle-free intersection graphs of line segments with large chromatic number