Box and Segment Intersection Graphs with Large Girth and Chromatic Number

DOI10.19086/AIC.25431MaRDI QIDQ5162871zbMATH OpenOpenAlexFDO

Authors James E. Davies

Publication date 5 November 2021

Published in Advances in Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

axis-aligned boxesintersection graphs of straight lines

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: We prove that there are intersection graphs of axis-aligned boxes in $mathbb{R}^3$ and intersection graphs of straight lines in $mathbb{R}^3$ that have arbitrarily large girth and chromatic number.

Recommendations

• Triangle-free intersection graphs of line segments with large chromatic number
• Grid intersection graphs and boxicity
• Turán-type results for intersection graphs of boxes
• Bounds on the chromatic number of intersection graphs of sets in the plane
• Extremal Results on Intersection Graphs of Boxes in $${\mathbb R}^d$$ R d
• Colouring triangle-free intersection graphs of boxes on the plane
• Triangle-free geometric intersection graphs with large chromatic number
• Chordal bipartite graphs with high boxicity
• On the chromatic number of intersection graphs of convex sets in the plane
• Clique chromatic numbers of intersection graphs

Cites work

• A short proof of the existence of highly chromatic hypergraphs without short cycles
• A Sparse Graham-Rothschild Theorem
• A survey of -boundedness
• Coloring intersection graphs of \(x\)-monotone curves in the plane
• Coloring rectangular blocks in 3-space
• Coloring relatives of intervals on the plane. I: Chromatic number versus girth
• Colour-critical graphs and hypergraphs
• Colouring triangle-free intersection graphs of boxes on the plane
• Dense induced bipartite subgraphs in triangle-free graphs
• Disjointness graphs of segments
• Disjointness graphs of segments in the space
• Graph Theory and Probability
• scientific article; zbMATH DE number 1002021 (Why is no real title available?)
• scientific article; zbMATH DE number 15377 (Why is no real title available?)
• scientific article; zbMATH DE number 2145236 (Why is no real title available?)
• scientific article; zbMATH DE number 3316912 (Why is no real title available?)
• Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
• On a Coloring Problem.
• On-line approach to off-line coloring problems on graphs with geometric representations
• Properties of Descartes' Construction of Triangle-Free Graphs with High Chromatic Number
• Ramsey's Theorem for n-Parameter Sets
• Regularity and Positional Games
• Separator theorems and Turán-type results for planar intersection graphs
• Studien zur Kombinatorik
• Triangle-free intersection graphs of line segments with large chromatic number
• Turán-type results for intersection graphs of boxes

Cited in

(8)

• Extremal Results on Intersection Graphs of Boxes in $${\mathbb R}^d$$ R d
• Disjointness graphs of short polygonal chains
• Ramsey properties of semilinear graphs
• Coloring lines and Delaunay graphs with respect to boxes
• Geometric Graphs with Exponential Chromatic Number and Arbitrary Girth
• Polynomial Gyárfás-Sumner conjecture for graphs of bounded boxicity
• Sparse bounded hop-spanners for geometric intersection graphs
• A solution to Ringel's circle problem

This page was built for publication: Box and Segment Intersection Graphs with Large Girth and Chromatic Number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5162871)