Triangle-free geometric intersection graphs with large chromatic number

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

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

Publication date: 6 November 2013

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

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.

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)

Cites Work

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

Cited In (18)

• Restricted frame graphs and a conjecture of Scott
• Triangle-free intersection graphs of line segments with large chromatic number
• Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
• Coloring triangle-free L-graphs with \(O (\log \log n)\) colors
• Coloring intersection graphs of arc-connected sets in the plane
• Intersection graphs of L-shapes and segments in the plane
• Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded
• Decomposition of Multiple Packings with Subquadratic Union Complexity
• On-line approach to off-line coloring problems on graphs with geometric representations
• 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
• Coloring triangle-free L-graphs with \(O(\log\log n)\) colors
• Box and Segment Intersection Graphs with Large Girth and Chromatic Number
• Secure multi-party convex hull protocol based on quantum homomorphic encryption
• Triangle‐free graphs with large chromatic number and no induced wheel
• 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)