RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2009 Volume 6, Pages 13–16 (Mi semr53)

This article is cited 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.

UDC: 519.172.2

MSC: 05C15

Received January 11, 2009, published January 26, 2009



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024