Triangle-free intersection graphs of line segments with large chromatic number
From MaRDI portal
(Redirected from 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
(73)- 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
- Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
- On graphs with no induced subdivision of \(K_4\)
- An intersection graph of straight lines
- Vertex-minor-closed classes are -bounded
- Coloring intersection graphs of arc-connected sets in the plane
- 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
- 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
- Chromatic number of intersection graphs of segments with two slopes (extended abstract)
- Decomposition of Multiple Packings with Subquadratic Union Complexity
- Kővári-Sós-Turán theorem for hereditary families
- On-line approach to off-line coloring problems on graphs with geometric representations
- Polynomial Gyárfás-Sumner conjecture for graphs of bounded boxicity
- Conflict-free coloring of string graphs
- Shift graphs, chromatic number and acyclic one-path orientations
- On tangencies among planar curves with an application to coloring L-shapes
- Coloring non-crossing strings
- Ramsey properties of semilinear graphs
- On tangencies among planar curves with an application to coloring L-shapes
- The chromatic number of {ISK4, diamond, bowtie}‐free graphs
- Hasse diagrams with large chromatic number
- Coloring triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors
- Triangle-free geometric intersection graphs with no large independent sets
- Coloring curves that cross a fixed curve
- Burling graphs, chromatic number, and orthogonal tree-decompositions
- Colouring polygon visibility graphs and their generalizations
- scientific article; zbMATH DE number 7559254 (Why is no real title available?)
- Induced subgraphs of graphs with large chromatic number. VI. Banana trees
- Burling graphs, chromatic number, and orthogonal tree-decompositions
- Amalgams and -boundedness
- Graphs of large chromatic number
- Excluding cycles with a fixed number of chords
- Box and Segment Intersection Graphs with Large Girth and Chromatic Number
- Scott's induced subdivision conjecture for maximal triangle-free graphs
- On the cop number of string graphs
- Coloring lines and Delaunay graphs with respect to boxes
- Coloring triangle-free rectangular frame intersection graphs with \(O(\log \log n)\) colors
- On the chromatic number of disjointness graphs of curves
- On a combinatorial application of ultrafilter theory: a new construction of triangle-free graphs with arbitrarily large chromatic number
- The -binding function of d-directional segment graphs
- Treewidth versus clique number. I: Graph classes with a forbidden structure
- The thickness of fan-planar graphs is at most three
- Constrained outer-string representations
- Chi-boundedness of graphs containing no cycles with k chords
- Disjointness graphs of segments in the space
- Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
- Coloring k k -free intersection graphs of geometric objects in the plane
- A survey of degree-boundedness
- Triangle‐free graphs with large chromatic number and no induced wheel
- Chromatic number of ISK4-free graphs
- Burling graphs revisited. I: New characterizations
- Outerstring graphs are -bounded
- Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors
- Induced subdivisions in \(K_{s,s}\)-free graphs with polynomial average degree
- Constrained outer-string representations
- Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
- Coloring intersection graphs of \(x\)-monotone curves in the plane
- 2P₃-free graphs that do not contain any induced subdivision of K₄ are 4-colorable
- Coloring Hasse diagrams and disjointness graphs of curves
- 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
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)
