Coloring k k -free intersection graphs of geometric objects in the plane

DOI10.1145/1377676.1377735MaRDI QIDQ3602935zbMATHOpenAlexFDO

Authors Jacob Fox, János Pach

Publication date 12 February 2009

Published in Proceedings of the twenty-fourth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1377676.1377735

Mathematics Subject Classification ID

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

Recommendations

• Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
• Bounds on the chromatic number of intersection graphs of sets in the plane
• Coloring curves that cross a fixed curve
• Coloring curves that cross a fixed curve
• Triangle-free intersection graphs of line segments with large chromatic number

Cited in

(24)

• 2-Layer k-Planar Graphs
• Coloring the complements of intersection graphs of geometric figures
• A Separator Theorem for String Graphs and Its Applications
• On the chromatic number of disjointness graphs of curves
• The discharging method in combinatorial geometry and the Pach-Sharir conjecture
• Tangencies between families of disjoint regions in the plane
• On planar intersection graphs with forbidden subgraphs
• Coloring intersection graphs of \(x\)-monotone curves in the plane
• Intersection patterns of curves
• Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
• Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar
• On disjoint crossing families in geometric graphs
• Coloring a set of touching strings
• Coloring curves that cross a fixed curve
• Maximum independent set in 2-direction outersegment graphs
• Coloring non-crossing strings
• Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
• Triangle-free intersection graphs of line segments with large chromatic number
• String graphs and incomparability graphs
• Coloring intersection graphs of arc-connected sets in the plane
• Geometric intersection patterns and the theory of topological graphs
• Many disjoint edges in topological graphs
• Coloring curves that cross a fixed curve
• \(k\)-quasi-planar graphs

This page was built for publication: Coloring k _k -free intersection graphs of geometric objects in the plane

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