Coloring triangle-free L-graphs with O ( n) colors

DOI10.1016/J.EJC.2023.103831arXiv2002.10755OpenAlexW3007920226MaRDI QIDQ6181998FDOQ6181998

Bartosz Walczak

Publication date: 23 January 2024

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: It is proved that triangle-free intersection graphs of $n$ L-shapes in the plane have chromatic number $O(loglogn)$. This improves the previous bound of $O(logn)$ (McGuinness, 1996) and matches the known lower bound construction (Pawlik et al., 2013).

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

zbMATH Keywords

chromatic numbertriangle-free intersection graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Coloring triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors
• Triangle-free geometric intersection graphs with large chromatic number
• Triangle-free intersection graphs of line segments with large chromatic number
• Title not available (Why is that?)
• Sur le coloriage des graphs
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Applications of a New Separator Theorem for String Graphs
• The max clique problem in classes of string-graphs
• Intersection graphs of L-shapes and segments in the plane
• Every planar graph is the intersection graph of segments in the plane
• On a Coloring Problem.
• Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
• Covering and coloring problems for relatives of intervals
• On the chromatic number of multiple interval graphs and overlap graphs
• Coloring intersection graphs of \(x\)-monotone curves in the plane
• Colouring arcwise connected sets in the plane. I
• Colouring arcwise connected sets in the plane. II
• Coloring intersection graphs of arc-connected sets in the plane
• Title not available (Why is that?)
• On bounding the chromatic number of L-graphs
• Title not available (Why is that?)
• On-line approach to off-line coloring problems on graphs with geometric representations
• A survey of χ‐boundedness
• Coloring curves that cross a fixed curve
• On grounded \(\llcorner\)-graphs and their relatives
• Circle graphs are quadratically χ‐bounded
• Outerstring Graphs are $\chi$-Bounded
• Improved bounds for colouring circle graphs

Cited In (1)

• Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded

This page was built for publication: Coloring triangle-free L-graphs with \(O (\log \log n)\) colors

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