Planar Graphs have Independence Ratio at least 3/13

Electronic Journal Of Combinatorics

Daniel W. Cranston¹ 

关键词: Independent sets;    Planar graphs;   

DOI  :  

学科分类：离散数学和组合数学

来源: Electronic Journal Of Combinatorics

【 摘 要 】

The 4 Color Theorem (4CT) implies that every $n$-vertex planar graph has an independent set of size at least $\frac{n}4$; this is best possible, as shown by the disjoint union of many copies of $K_4$.  In 1968, Erdős asked whether this bound on independen

【 授权许可】

Others