Triangle-free geometric intersection graphs with no large independent sets

DOI10.1007/s00454-014-9645-yzbMath1307.05180arXiv1404.0169OpenAlexW2091843659WikidataQ59407086 ScholiaQ59407086MaRDI QIDQ2256591

Bartosz Walczak

Publication date: 19 February 2015

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

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

zbMATH Keywords

intersection graphfractional chromatic numbertriangle-freemaximum independent setline segments

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (4)

Quasiplanar graphs, string graphs, and the Erdős-Gallai problem ⋮ Coloring lines and Delaunay graphs with respect to boxes ⋮ Ramsey-Turán numbers for semi-algebraic graphs ⋮ Restricted frame graphs and a conjecture of Scott

Cites Work

• Triangle-free geometric intersection graphs with large chromatic number
• Triangle-free intersection graphs of line segments with large chromatic number
• Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
• On the maximum number of edges in topological graphs with no four pairwise crossing edges
• Applications of the crossing number
• Colouring arcwise connected sets in the plane. I

This page was built for publication: Triangle-free geometric intersection graphs with no large independent sets