Independent sets in triangle-free cubic planar graphs

DOI10.1016/j.jctb.2005.07.009zbMath1087.05044OpenAlexW2028168192MaRDI QIDQ2490253

Robin Thomas, Christopher Carl Heckman

Publication date: 28 April 2006

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2005.07.009

zbMATH Keywords

stable setmaximum degree three

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (20)

Transversals and independence in linear hypergraphs with maximum degree two ⋮ On bipartization of cubic graphs by removal of an independent set ⋮ On line graphs of subcubic triangle-free graphs ⋮ Maximum induced forests in graphs of bounded treewidth ⋮ Independent sets in \(\{\text{claw}, K_4 \}\)-free 4-regular graphs ⋮ Relating the independence number and the dissociation number ⋮ On \(k\)-domination and \(j\)-independence in graphs ⋮ Leapfrog fullerenes have many perfect matchings ⋮ Independent sets in graphs ⋮ Lower Bounds on the Size of Maximum Independent Sets and Matchings in Hypergraphs of Rank Three ⋮ Packing and covering odd cycles in cubic plane graphs with small faces ⋮ Packing and covering odd cycles in cubic plane graphs with small faces ⋮ Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach ⋮ Large Independent Sets in Subquartic Planar Graphs ⋮ Large Independent Sets in Triangle-Free Planar Graphs ⋮ Zero forcing in claw-free cubic graphs ⋮ Multiple Domination ⋮ Volume estimates for equiangular hyperbolic Coxeter polyhedra ⋮ The Fano Plane and the Strong Independence Ratio in Hypergraphs of Maximum Degree 3 ⋮ Subcubic triangle-free graphs have fractional chromatic number at most 14/5

Cites Work

• Independence in graphs with maximum degree four
• Planar Ramsey numbers
• 11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)
• The Fractional Chromatic Number of Graphs of Maximum Degree at Most Three
• A Theorem on Planar Graphs
• Girth and fractional chromatic number of planar graphs
• Some Ramsey-Type Numbers and the Independence Ratio
• A (<5)-Colour Theorem for Planar Graphs
• Size and independence in triangle‐free graphs with maximum degree three
• A new proof of the independence ratio of triangle-free cubic graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Independent sets in triangle-free cubic planar graphs