Near-proper vertex 2-colorings of sparse graphs
2010
A graph G is (2, 1)-colorable if its vertices can be partitioned into subsets V 1 and V 2 such that each component in G[V 1] contains at most two vertices while G[V 2] is edgeless. We prove that every graph with maximum average degree mad(G) < 7/3 is (2, 1)-colorable. It follows that every planar graph with girth at least 14 is (2, 1)-colorable. We also construct a planar graph G n with mad (G n ) = (18n − 2)/(7n − 1) that is not (2, 1)-colorable.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
4
References
7
Citations
NaN
KQI