Triangle-free geometric intersection graphs with large chromatic number

DOI10.1007/S00454-013-9534-9zbMATH Open1275.05038OpenAlexW2019696395WikidataQ59303575 ScholiaQ59303575MaRDI QIDQ377499FDOQ377499

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

Publication date 6 November 2013

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numbertriangle-freeclique numberintersection graphL-shapescoloring geometric objects in the planeon-line coloring of intervals on the line

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: Several classical constructions illustrate the fact that the chromatic number of a graph can be arbitrarily large compared to its clique number. However, until very recently, no such construction was known for intersection graphs of geometric objects in the plane. We provide a general construction that for any arc-connected compact set $X$ in $mathbb{R}^2$ that is not an axis-aligned rectangle and for any positive integer $k$ produces a family $mathcalF$ of sets, each obtained by an independent horizontal and vertical scaling and translation of $X$, such that no three sets in $mathcalF$ pairwise intersect and $chi(mathcalF)>k$. This provides a negative answer to a question of Gyarfas and Lehel for L-shapes. With extra conditions, we also show how to construct a triangle-free family of homothetic (uniformly scaled) copies of a set with arbitrarily large chromatic number. This applies to many common shapes, like circles, square boundaries, and equilateral L-shapes. Additionally, we reveal a surprising connection between coloring geometric objects in the plane and on-line coloring of intervals on the line.

Recommendations

• Triangle-free intersection graphs of line segments with large chromatic number
• Bounds on the chromatic number of intersection graphs of sets in the plane
• Coloring triangle-free rectangular frame intersection graphs with \(O(\log \log n)\) colors
• On-line approach to off-line coloring problems on graphs with geometric representations
• Triangle-free geometric intersection graphs with no large independent sets

Cites work

• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• Coloring intersection graphs of \(x\)-monotone curves in the plane
• Corrigendum
• Covering and coloring polygon-circle graphs
• Covering and coloring problems for relatives of intervals
• On a Coloring Problem.
• On the chromatic number of intersection graphs of convex sets in the plane
• On the chromatic number of multiple interval graphs and overlap graphs
• Research Problems in Discrete Geometry
• Sur le coloriage des graphs
• Triangle-free intersection graphs of line segments with large chromatic number

Cited in

(22)

• Coloring triangle-free L-graphs with \(O(\log\log n)\) colors
• Decomposition of Multiple Packings with Subquadratic Union Complexity
• Coloring triangle-free rectangular frame intersection graphs with \(O(\log \log n)\) colors
• Contact graphs of boxes with unidirectional contacts
• scientific article; zbMATH DE number 2145236 (Why is no real title available?)
• Intersection graphs of L-shapes and segments in the plane
• Secure multi-party convex hull protocol based on quantum homomorphic encryption
• Coloring lines and Delaunay graphs with respect to boxes
• Triangle‐free graphs with large chromatic number and no induced wheel
• Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
• Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded
• 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
• Restricted frame graphs and a conjecture of Scott
• On-line approach to off-line coloring problems on graphs with geometric representations
• Triangle-free intersection graphs of line segments with large chromatic number
• Outerstring graphs are \(\chi \)-bounded
• Coloring triangle-free L-graphs with \(O (\log \log n)\) colors
• Coloring intersection graphs of arc-connected sets in the plane
• Box and Segment Intersection Graphs with Large Girth and Chromatic Number
• Burling graphs revisited. I: New characterizations

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

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