Triangle-free planar graphs with the smallest independence number

Jan Mus\'ilek; Ond\v{r}ej Pangr\'ac; Tom\'a\v{s} Masa\v{r}\'ik; Zden\v{e}k Dvo\v{r}\'ak

arxiv: 1606.06265 · v1 · pith:XP44J53Unew · submitted 2016-06-20 · 🧮 math.CO · cs.DM

Triangle-free planar graphs with the smallest independence number

Zden\v{e}k Dvo\v{r}\'ak , Tom\'a\v{s} Masa\v{r}\'ik , Jan Mus\'ilek , Ond\v{r}ej Pangr\'ac This is my paper

classification 🧮 math.CO cs.DM

keywords planartriangle-freeclassgraphsindependentinfiniteleastn-vertex

0 comments

read the original 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.

This paper has not been read by Pith yet.

Triangle-free planar graphs with the smallest independence number

discussion (0)