Decomposition of class II graphs into two class I graphs
Decomposition of class II graphs into two class I graphs
复制标题
将 II 类图分解为两个 I 类图
DOI：
10.1016/j.disc.2023.113610
复制
发表时间：
2023
影响因子：
0.8
通讯作者：
Zhao, Yue
中科院分区：
文献类型：
--
作者：
Cao, Yan;Jing, Guangming;Luo, Rong;Mkrtchyan, Vahan;Zhang, Cun-Quan;Zhao, Yue
摘要Mkrtchyan和Steffen（2012）[3]证明了每个II类简单图都可以分解为一个最大Δ-边可着色子图和一个匹配。进一步证明了每个色指数为Δ（G）+ k（k≥ 1）的图G都可以分解为一个最大Δ（G）-边可着色子图（不一定是I类）和一个k-边可着色子图.本文首先将他们的结果推广到多重图，证明了每个重数为μ的多重图G都可以分解为一个最大Δ（G）-边可着色子图和一个最大度不超过μ的子图.然后证明了每个色指数为Δ（G）+ k的图G都可以分解为两个I类子图H1和H2，使得Δ（H1）= Δ（G）和Δ（H2）= k，这是他们猜想的一个变化.
Abstract Mkrtchyan and Steffen (2012)[3] showed that every class II simple graph can be decomposed into a maximum Δ-edge-colorable subgraph and a matching. They further conjectured that every graph G with chromatic index Δ (G)+ k (k≥ 1) can be decomposed into a maximum Δ (G)-edge-colorable subgraph (not necessarily class I) and a k-edge-colorable subgraph. In this paper, we first generalize their result to multigraphs and show that every multigraph G with multiplicity μ can be decomposed into a maximum Δ (G)-edge-colorable subgraph and a subgraph with maximum degree at most μ. Then we prove that every graph G with chromatic index Δ (G)+ k can be decomposed into two class I subgraphs H 1 and H 2 such that Δ (H 1)= Δ (G) and Δ (H 2)= k, which is a variation of their conjecture.
登录
查看更多内容
II 类图的最大 Δ 边可着色子图
影响因子：
0.9
作者：
V. Mkrtchyan;E. Steffen
通讯作者：
E. Steffen
关于三次图中的不相交匹配
DOI：
10.1016/j.disc.2010.02.007
发表时间：
2008
期刊：
Discret. Math.
影响因子：
--
作者：
V. Mkrtchyan;S. S. Petrosyan;Gagik N. Vardanyan
通讯作者：
Gagik N. Vardanyan
近似最大 3 边可着色子图问题
DOI：
10.1016/j.disc.2008.11.017
发表时间：
2009
期刊：
Discret. Math.
影响因子：
--
作者：
Romeo Rizzi
通讯作者：
Romeo Rizzi
影响因子：
0.8
作者：
Albertson, MO;Haas, R
通讯作者：
Haas, R