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

DOI10.1016/J.EJC.2023.103831MaRDI QIDQ6181998zbMATH OpenOpenAlexFDO

Authors Bartosz Walczak

Publication date 23 January 2024

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

Copyright license Creative Commons Attribution 4.0 International

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)

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).

Recommendations

• Coloring triangle-free L-graphs with O( n) colors
• Coloring triangle-free rectangular frame intersection graphs with \(O(\log \log n)\) colors
• Coloring triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors
• On bounding the chromatic number of L-graphs
• Triangle-free geometric intersection graphs with large chromatic number

Cites work

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

Cited in

(4)

• Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded
• On tangencies among planar curves with an application to coloring L-shapes
• Coloring triangle-free L-graphs with O( n) colors
• A survey of degree-boundedness

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)