Grounded L-graphs are polynomially -bounded

DOI10.1007/S00454-023-00592-ZMaRDI QIDQ6142355zbMATH OpenFDO

Authors James E. Davies, Tomasz Krawczyk, Rose McCarty, Bartosz Walczak

Publication date 21 December 2023

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

\( \chi \)-boundednessgeometric intersection graphs

Mathematics Subject Classification ID

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

Abstract: A grounded L-graph is the intersection graph of a collection of "L" shapes whose topmost points belong to a common horizontal line. We prove that every grounded L-graph with clique number $omega$ has chromatic number at most $17omeg{a}^4$. This improves the doubly-exponential bound of McGuinness and generalizes the recent result that the class of circle graphs is polynomially $chi$-bounded. We also survey $chi$-boundedness problems for grounded geometric intersection graphs and give a high-level overview of recent techniques to obtain polynomial bounds.

Recommendations

• Graphs of bounded cliquewidth are polynomially -bounded
• Graphs of bounded twin-width are quasi-polynomially -bounded
• Outerstring graphs are -bounded
• Outerstring graphs are \(\chi\)-bounded
• On bounding the chromatic number of L-graphs
• Bounds to the chromatic polynomial of a graph
• On \((\delta, \chi)\)-bounded families of graphs
• Classes of graphs with no long cycle as a vertex-minor are polynomially \(\chi\)-bounded
• Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs
• On grounded -graphs and their relatives

Cites work

• A survey of -boundedness
• A Turán-type theorem on chords of a convex polygon
• Algorithmic graph theory and perfect graphs
• Applications of a new separator theorem for string graphs
• Circle graphs are quadratically χ‐bounded
• Coloring and maximum independent set of rectangles
• Coloring intersection graphs of \(x\)-monotone curves in the plane
• Coloring intersection graphs of arc-connected sets in the plane
• Coloring triangle-free L-graphs with \(O (\log \log n)\) colors
• Coloring triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors
• Colouring arcwise connected sets in the plane. I
• Covering and coloring polygon-circle graphs
• scientific article; zbMATH DE number 4108789 (Why is no real title available?)
• scientific article; zbMATH DE number 2145236 (Why is no real title available?)
• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• Improved bounds for colouring circle graphs
• Intersection graphs of rays and grounded segments
• Max point-tolerance graphs
• Maximum weight independent sets and cliques in intersection graphs of filaments
• 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
• Refining the hierarchies of classes of geometric intersection graphs
• The max clique problem in classes of string-graphs
• Triangle-free geometric intersection graphs with large chromatic number

Cited in

(5)

• Graphs of bounded twin-width are quasi-polynomially -bounded
• Constrained outer-string representations
• A survey of degree-boundedness
• Polynomial Gyárfás-Sumner conjecture for graphs of bounded boxicity
• Constrained outer-string representations

This page was built for publication: Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded

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