Triangle-free geometric intersection graphs with no large independent sets

DOI10.1007/S00454-014-9645-YMaRDI QIDQ2256591zbMATH OpenOpenAlexWikidataFDO

Authors Bartosz Walczak

Publication date 19 February 2015

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/1404.0169

zbMATH Keywords

fractional chromatic numberintersection graphline segmentsmaximum independent settriangle-free

Mathematics Subject Classification ID

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

Abstract: It is proved that there are triangle-free intersection graphs of line segments in the plane with arbitrarily small ratio between the maximum size of an independent set and the total number of vertices.

Recommendations

• scientific article; zbMATH DE number 1500690
• Triangle-free geometric intersection graphs with large chromatic number
• Triangle-free intersection graphs of line segments with large chromatic number
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• Triangle-free planar graphs with the smallest independence number

Cites work

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

Cited in

(12)

• Restricted frame graphs and a conjecture of Scott
• Triangle-free geometric intersection graphs with large chromatic number
• scientific article; zbMATH DE number 1500690 (Why is no real title available?)
• Unique intersectability of diamond-free graphs
• Intersection patterns of curves
• Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
• Coloring lines and Delaunay graphs with respect to boxes
• Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
• Discrete geometry. Abstracts from the workshop held January 21--26, 2024
• Ramsey-Turán numbers for semi-algebraic graphs
• The -binding function of d-directional segment graphs
• An 11/6-approximation algorithm for vertex cover on string graphs

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

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