|
Diskretnyi Analiz i Issledovanie Operatsii, 2009, Volume 16, Issue 2, Pages 16–20
(Mi da565)
|
|
|
|
This article is cited in 18 scientific papers (total in 18 papers)
Near-proper vertex 2-colorings of sparse graphs
O. V. Borodina, A. O. Ivanovab a S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
b Institute of Mathematics at Yakutsk State University, Yakutsk, Russia
Abstract:
A graph $G$ is $(2,1)$-colorable if its vertices can be partitioned into subsets $V_1$ and $V_2$ such that in $G[V_1]$ any component contains at most two vertices while $G[V_2]$ is edgeless. We prove that every graph $G$ with the maximum average degree $\mathrm{mad}(G)$ smaller than 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 $\mathrm{mad}(G_n)=(18n-2)/(7n-1)$ that is not $(2,1)$-colorable. Bibl. 5.
Keywords:
planar graph, girth, coloring, partition.
Received: 09.02.2008
Citation:
O. V. Borodin, A. O. Ivanova, “Near-proper vertex 2-colorings of sparse graphs”, Diskretn. Anal. Issled. Oper., 16:2 (2009), 16–20; J. Appl. Industr. Math., 4:1 (2010), 21–23
Linking options:
https://www.mathnet.ru/eng/da565 https://www.mathnet.ru/eng/da/v16/i2/p16
|
Statistics & downloads: |
Abstract page: | 624 | Full-text PDF : | 113 | References: | 58 | First page: | 3 |
|