Abstract | ||
---|---|---|
We prove that every triangle-free planar graph on n vertices with maximum degree three has an independent set with size at least 3/8n. This was suggested and later conjectured by Albertson, Bollobas, and Tucker. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1016/j.jctb.2005.07.009 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
maximum degree three,planar graph,maximum degree,n vertex,triangle-free cubic planar graph,independent set,triangle-free,graph,triangle-free planar graph,stable set | Discrete mathematics,Combinatorics,Outerplanar graph,Planar straight-line graph,Cubic graph,Polyhedral graph,Independent set,Book embedding,Triangle-free graph,Mathematics,Maximal independent set | Journal |
Volume | Issue | ISSN |
96 | 2 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
13 | 0.77 | 8 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Christopher Carl Heckman | 1 | 38 | 4.66 |
Robin Thomas | 2 | 457 | 35.92 |