Triangle-free intersection graphs of line segments with large chromatic number
From MaRDI portal
Publication:401487
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.
Recommendations
- Triangle-free geometric intersection graphs with large chromatic number
- Coloring k k -free intersection graphs of geometric objects in the plane
- Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
- Bounds on the chromatic number of intersection graphs of sets in the plane
- Triangle-free graphs with large chromatic numbers
Cites work
- scientific article; zbMATH DE number 1002021 (Why is no real title available?)
- scientific article; zbMATH DE number 4183452 (Why is no real title available?)
- scientific article; zbMATH DE number 3050594 (Why is no real title available?)
- Coloring intersection graphs of \(x\)-monotone curves in the plane
- Coloring relatives of intervals on the plane. I: Chromatic number versus girth
- Colouring arcwise connected sets in the plane. I
- Colouring arcwise connected sets in the plane. II
- Covering and coloring problems for relatives of intervals
- On a Coloring Problem.
- Research Problems in Discrete Geometry
- Some geometric applications of Dilworth's theorem
- Sur le coloriage des graphs
- Triangle-free geometric intersection graphs with large chromatic number
Cited in
(58)- On tangencies among planar curves with an application to coloring L-shapes
- On tangencies among planar curves with an application to coloring L-shapes
- Coloring lines and Delaunay graphs with respect to boxes
- Disjointness graphs of short polygonal chains
- Burling graphs revisited. II: Structure
- Burling graphs revisited. III: Applications to \(\chi \)-boundedness
- Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
- Graphs of large chromatic number
- Coloring triangle-free L-graphs with \(O (\log \log n)\) colors
- Amalgams and \(\chi\)-boundedness
- Hasse diagrams with large chromatic number
- Coloring polygon visibility graphs and their generalizations
- Decomposition of Multiple Packings with Subquadratic Union Complexity
- Burling graphs, chromatic number, and orthogonal tree-decompositions
- Colouring arcwise connected sets in the plane. I
- Coloring triangle-free rectangular frame intersection graphs with \(O(\log \log n)\) colors
- The chromatic number of graphs with no induced subdivision of \(K_4\)
- Chromatic number of ISK4-free graphs
- Scott's induced subdivision conjecture for maximal triangle-free graphs
- On the chromatic number of disjointness graphs of curves
- An intersection graph of straight lines
- The chromatic number of {ISK4, diamond, bowtie}‐free graphs
- Coloring intersection graphs of \(x\)-monotone curves in the plane
- Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
- Some remarks on graphs with no induced subdivision of \(K_4\)
- scientific article; zbMATH DE number 7559254 (Why is no real title available?)
- Triangle‐free graphs with large chromatic number and no induced wheel
- Refining the hierarchies of classes of geometric intersection graphs
- On the speed of algebraically defined graph classes
- Refining the hierarchies of classes of geometric intersection graphs
- Burling graphs, chromatic number, and orthogonal tree-decompositions
- Coloring Hasse diagrams and disjointness graphs of curves
- Conflict-free coloring of string graphs
- Coloring k k -free intersection graphs of geometric objects in the plane
- Induced subgraphs of graphs with large chromatic number. VI. Banana trees
- Disjointness graphs of segments in the space
- Coloring curves that cross a fixed curve
- Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
- Coloring triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors
- Triangle-free geometric intersection graphs with no large independent sets
- Triangle-free geometric intersection graphs with large chromatic number
- Quasi-planar Graphs
- Restricted frame graphs and a conjecture of Scott
- Coloring non-crossing strings
- On-line approach to off-line coloring problems on graphs with geometric representations
- Outerstring graphs are \(\chi \)-bounded
- Coloring intersection graphs of arc-connected sets in the plane
- Box and Segment Intersection Graphs with Large Girth and Chromatic Number
- From \(\chi\)- to \(\chi_p\)-bounded classes
- Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors
- Treewidth versus clique number. I: Graph classes with a forbidden structure
- Graph theory. Abstracts from the workshop held January 2--8, 2022
- The thickness of fan-planar graphs is at most three
- Pure pairs. II: Excluding all subdivisions of a graph
- Ramsey properties of semilinear graphs
- Excluding cycles with a fixed number of chords
- Burling graphs revisited. I: New characterizations
- On graphs with no induced subdivision of \(K_4\)
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)
