Triangle-free intersection graphs of line segments with large chromatic number
From MaRDI portal
Publication:401487
DOI10.1016/J.JCTB.2013.11.001zbMATH Open1300.05106arXiv1209.1595OpenAlexW3101282841MaRDI QIDQ401487FDOQ401487
Bartosz Walczak, William T. Trotter, Tomasz Krawczyk, Jakub Kozik, Michał Lasoń, Arkadiusz Pawlik, Piotr Micek
Publication date: 27 August 2014
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Abstract: In the 1970s, Erdos asked whether the chromatic number of intersection graphs of line segments in the plane is bounded by a function of their clique number. We show the answer is no. Specifically, for each positive integer , we construct a triangle-free family of line segments in the plane with chromatic number greater than . Our construction disproves a conjecture of Scott that graphs excluding induced subdivisions of any fixed graph have chromatic number bounded by a function of their clique number.
Full work available at URL: https://arxiv.org/abs/1209.1595
Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Research Problems in Discrete Geometry
- Triangle-free geometric intersection graphs with large chromatic number
- Sur le coloriage des graphs
- On a Coloring Problem.
- Coloring relatives of intervals on the plane. I: Chromatic number versus girth
- Covering and coloring problems for relatives of intervals
- Coloring intersection graphs of \(x\)-monotone curves in the plane
- Some geometric applications of Dilworth's theorem
- Colouring arcwise connected sets in the plane. I
- Colouring arcwise connected sets in the plane. II
Cited In (56)
- Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
- On tangencies among planar curves with an application to coloring L-shapes
- On tangencies among planar curves with an application to coloring L-shapes
- Graphs of large chromatic number
- Coloring lines and Delaunay graphs with respect to boxes
- The chromatic number of graphs with no induced subdivision of \(K_4\)
- Restricted frame graphs and a conjecture of Scott
- From \(\chi\)- to \(\chi_p\)-bounded classes
- Pure pairs. II: Excluding all subdivisions of a graph
- Triangle-free geometric intersection graphs with large chromatic number
- On graphs with no induced subdivision of \(K_4\)
- Disjointness graphs of short polygonal chains
- Burling graphs revisited. II: Structure
- Burling graphs revisited. III: Applications to \(\chi \)-boundedness
- Coloring triangle-free L-graphs with \(O (\log \log n)\) colors
- Coloring intersection graphs of arc-connected sets in the plane
- Colouring arcwise connected sets in the plane. I
- Some remarks on graphs with no induced subdivision of \(K_4\)
- On the speed of algebraically defined graph classes
- Graph theory. Abstracts from the workshop held January 2--8, 2022
- Quasi-planar Graphs
- Decomposition of Multiple Packings with Subquadratic Union Complexity
- Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure
- On-line approach to off-line coloring problems on graphs with geometric representations
- Conflict-free coloring of string graphs
- Ramsey properties of semilinear graphs
- Coloring non-crossing strings
- The chromatic number of {ISK4, diamond, bowtie}‐free graphs
- Hasse diagrams with large chromatic number
- Planar point sets determine many pairwise crossing segments
- Burling graphs, chromatic number, and orthogonal tree-decompositions
- Coloring curves that cross a fixed curve
- Coloring triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors
- Triangle-free geometric intersection graphs with no large independent sets
- Outerstring Graphs are $\chi$-Bounded
- Amalgams and χ-Boundedness
- Title not available (Why is that?)
- Burling graphs, chromatic number, and orthogonal tree-decompositions
- Cops and robbers on intersection graphs
- Induced subgraphs of graphs with large chromatic number. VI. Banana trees
- Box and Segment Intersection Graphs with Large Girth and Chromatic Number
- Excluding cycles with a fixed number of chords
- On the chromatic number of disjointness graphs of curves
- The thickness of fan-planar graphs is at most three
- Disjointness graphs of segments in the space
- Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
- Triangle‐free graphs with large chromatic number and no induced wheel
- Chromatic number of ISK4-free graphs
- Burling graphs revisited. I: New characterizations
- Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors
- Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
- Coloring intersection graphs of \(x\)-monotone curves in the plane
- Coloring polygon visibility graphs and their generalizations
- Refining the hierarchies of classes of geometric intersection graphs
- Refining the hierarchies of classes of geometric intersection graphs
- Coloring Hasse diagrams and disjointness graphs of curves
This page was built for publication: Triangle-free intersection graphs of line segments with large chromatic number
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q401487)
