平面图的(F, Fd)-分解问题
Vertex Partitions of Graphs into a Forest and a Forest with Bounded Maximum Degree
摘要:
图G的(F, F
d)-分解是指将G的顶点集合划分为两个子集F和F
d，使得G[F]为森林，G[F
d]为最大度至多为d的森林。本文证明了每一个不含4-圈和5-圈的平面图都存在(F, F
d)-分解。
Abstract:
An (F, Fd)-partition of a graph G is a vertex partition of its vertex set into subsets F and Fd such that G[F] is a forest, while G[Fd] is a forest of maximum degree at most d. In this paper, we prove that every planar graph without 4-cycles and 5-cycles admits an (F, Fd)-partition.
参考文献
|
[1]
|
Appel, K. and Haken, W. (1977) Every Planar Map Is Four Colorable. Part I: Discharging. Illinois Journal of Mathematics, 21, 429-490.
[Google Scholar] [CrossRef]
|
|
[2]
|
Appel, K. and Haken, W. (1977) Every Planar Map Is Four Colorable. Part II: Reducibility. Illinois Journal of Mathematics, 21, 491-567.
[Google Scholar] [CrossRef]
|
|
[3]
|
Borodin, O.V. (1976) A Proof of Grunbaum’s Conjecture on the Acyclic 5-Colorability of Planar Graphs (Russian). Doklady Akademii nauk SSSR, 231, 18-20.
|
|
[4]
|
Poh, K.S. (1990) On the Linear Vertex-Arboricity of a Plane Graph. Journal of Graph Theory, 14, 73-75.
[Google Scholar] [CrossRef]
|
|
[5]
|
Chartrand, G. and Kronk, H.V. (1969) The Point-Arboricity of Planar Graphs. Journal of the London Mathematical Society, 1, 612-616.
[Google Scholar] [CrossRef]
|
|
[6]
|
Raspaud, A. and Wang, W. (2011) On the Vertex-Arboricity of Planar Graphs. European Journal of Combinatorics, 52, 1004-1010.
|
|
[7]
|
Chen, M. and Raspaud, A. (2012) Vertex-Arboricity of Planar Graphs without Intersecting Triangles. European Journal of Combinatorics, 33, 905-923.
[Google Scholar] [CrossRef]
|
|
[8]
|
Dross, F. and Montassier, M. (2015) Partitioning a Triangle-Free Planar Graph into a Forest and a Forest of Bounded Degree. Electronic Notes in Discrete Mathematics, 49, 269-275.
[Google Scholar] [CrossRef]
|