Name
Abstract | ||
|---|---|---|
A graph G is (1,1)-colorable if its vertices can be partitioned into subsets V1 and V2 such that every vertex in G[Vi] has degree at most 1 for each i∈{1,2}. We prove that every graph with maximum average degree at most 145 is (1,1)-colorable. In particular, it follows that every planar graph with girth at least 7 is (1,1)-colorable. On the other hand, we construct graphs with maximum average degree arbitrarily close to 145 (from above) that are not (1,1)-colorable. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.disc.2013.07.014 | Discrete Mathematics |
Keywords | DocType | Volume |
Improper coloring,Sparse graph,Maximum average degree,Planar graph | Journal | 313 |
Issue | ISSN | Citations |
22 | 0012-365X | 15 |
PageRank | References | Authors |
0.89 | 8 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oleg V. Borodin | 1 | 639 | 67.41 |
| Alexandr V. Kostochka | 2 | 682 | 89.87 |
| Matthew Yancey | 3 | 73 | 8.59 |