Planar graphs have independence ratio at least 3/13

zbMath1344.05051arXiv1609.06010MaRDI QIDQ311579

Daniel W. Cranston, Landon Rabern

Publication date: 13 September 2016

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

planar graphsindependent sets

Mathematics Subject Classification ID

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

Related Items

Large immersions in graphs with independence number 3 and 4, 3‐Degenerate induced subgraph of a planar graph, Special issue in honour of Landon Rabern, Induced 2-degenerate subgraphs of triangle-free planar graphs, Planar graphs are \(9/2\)-colorable, Planar graphs without cycles of length 4 or 5 are \((11 : 3)\)-colorable

Cites Work

• Unnamed Item
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• A lower bound for the independence number of a planar graph
• The Rectilinear Steiner Tree Problem is $NP$-Complete