Triangle-free planar graphs with the smallest independence number

DOI10.1002/JGT.22406zbMATH Open1454.05082arXiv1606.06265OpenAlexW2469666287MaRDI QIDQ4630003FDOQ4630003

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)

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.

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

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

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)

Cited In (7)

• Planar graphs have independence ratio at least 3/13
• Independence number of 2-factor-plus-triangles graphs
• Every triangle-free planar graph has a planar upward drawing
• Every collinear set in a planar graph is free
• Independent sets in triangle-free cubic planar graphs
• On the tightness of the \(\frac {5}{14}\) independence ratio
• On sufficient conditions for planar graphs to be 5-flexible

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)