Triangle-free planar graphs with the smallest independence number

DOI10.1002/JGT.22406MaRDI QIDQ4630003zbMATHOpenAlexFDO

Authors Zdeněk Dvořák, Tomáš Masařík, Jan Musílek, Ondřej Pangrác

Publication date 28 March 2019

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

independent setplanar graphtriangle-free graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75)

Abstract: Steinberg and Tovey proved that every n-vertex planar triangle-free graph has an independent set of size at least (n+1)/3, and described an infinite class of tight examples. We show that all n-vertex planar triangle-free graphs except for this one infinite class have independent sets of size at least (n+2)/3.

Recommendations

• Triangle-free planar graphs with small independence number
• Independent sets in triangle-free cubic planar graphs
• Large independent sets in triangle-free planar graphs
• Large independent sets in triangle-free planar graphs
• Large independent sets in triangle-free cubic graphs: beyond planarity

Cited in

(10)

• Large independent sets in triangle-free cubic graphs: beyond planarity
• Triangle-free planar graphs with small independence number
• On sufficient conditions for planar graphs to be 5-flexible
• Every triangle-free planar graph has a planar upward drawing
• Triangle-free geometric intersection graphs with no large independent sets
• Independent sets in triangle-free cubic planar graphs
• Planar graphs have independence ratio at least 3/13
• Large independent sets in triangle-free planar graphs
• On the tightness of the \(\frac {5}{14}\) independence ratio
• Independence number of 2-factor-plus-triangles graphs

This page was built for publication: Triangle-free planar graphs with the smallest independence number

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