论文标题
某些禁忌子图的非负特性图的分解
Decompositions of graphs of nonnegative characteristic with some forbidden subgraphs
论文作者
论文摘要
图$ g $的a {\ em $（d，h）$ - 分解}是订单对$（d，h）$，因此$ h $是$ g $的子图，其中$ h $最大的$ h $和$ d $是$ g-e（h）$ g-e（h）$ d $的最高度。如果$ g $具有$（d，h）$ - 分解，则图$ g $是{\ em $（d，h）$ - emposable}。令$ g $为非负特性表面中的图形。在本文中，我们证明了以下结果。 （1）如果$ g $没有和弦$ 5 $ - 或和弦$ 6 $ -Cycles或Conconcles $ 7 $ -CYCLE，则没有相邻的$ 4 $ -CYCLE，则$ G $是$（3,1）$ - 可分解的，这概括了Chen，Zhu and Zhu and Zhu and Wang [computs computs computs computs comput。数学。 Appl，56（2008）2073--2078]和张的结果[评论。数学。大学。 Carolin，54（3）（2013）339--344]。 （2）如果$ g $没有$ i $ -cycles或$ j $ -cycles对于任何子集$ \ {i，j \} \ subseteq \ {3,4,4,6 \} $是$（2,1）$ - 可分解的，这概括了Dong和dong和XU [dong and XU]的结果。 alg。 and Appl。，1（2）（2009），291--297]。
A {\em $(d,h)$-decomposition} of a graph $G$ is an order pair $(D,H)$ such that $H$ is a subgraph of $G$ where $H$ has the maximum degree at most $h$ and $D$ is an acyclic orientation of $G-E(H)$ of maximum out-degree at most $d$. A graph $G$ is {\em $(d, h)$-decomposable} if $G$ has a $(d,h)$-decomposition. Let $G$ be a graph embeddable in a surface of nonnegative characteristic. In this paper, we prove the following results. (1) If $G$ has no chord $5$-cycles or no chord $6$-cycles or no chord $7$-cycles and no adjacent $4$-cycles, then $G$ is $(3,1)$-decomposable, which generalizes the results of Chen, Zhu and Wang [Comput. Math. Appl, 56 (2008) 2073--2078] and the results of Zhang [Comment. Math. Univ. Carolin, 54(3) (2013) 339--344]. (2) If $G$ has no $i$-cycles nor $j$-cycles for any subset $\{i,j\}\subseteq \{3,4,6\}$ is $(2,1)$-decomposable, which generalizes the results of Dong and Xu [Discrete Math. Alg. and Appl., 1(2) (2009), 291--297].
