|
Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports], 2009, Volume 6, Pages 13–16
(Mi semr53)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
Research papers
Partitioning sparse plane graphs into two induced subgraphs of small degree
O. V. Borodina, A. O. Ivanovab a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
b Institute for Mathematics and Informatics, Yakutsk State University
Abstract:
A graph $G$ is said to be $(a,b)$-partitionable for positive integers $a$, $b$ if its vertices can be partitioned into subsets $V_1$ and $V_2$ such that in $G[V_1]$ any path contains at most a vertices and in $G[V_2]$ any path contains at most $b$ vertices. We prove that every planar graph of girth $8$ is $(2,2)$-partitionable.
Keywords:
planar graph, coloring, vertex partition.
Received January 11, 2009, published January 26, 2009
Citation:
O. V. Borodin, A. O. Ivanova, “Partitioning sparse plane graphs into two induced subgraphs of small degree”, Sib. Èlektron. Mat. Izv., 6 (2009), 13–16
Linking options:
https://www.mathnet.ru/eng/semr53 https://www.mathnet.ru/eng/semr/v6/p13
|
Statistics & downloads: |
Abstract page: | 346 | Full-text PDF : | 56 | References: | 48 |
|