A 2-Bisection with Small Number of Monochromatic Edges of a Claw-Free Cubic Graph
A 2-Bisection with Small Number of Monochromatic Edges of a Claw-Free Cubic Graph
复制标题
无爪三次图的具有少量单色边的二等分
DOI：
10.1007/s00373-023-02611-5
复制
发表时间：
2023
影响因子：
0.7
通讯作者：
Kenta Ozeki
中科院分区：
文献类型：
--
作者：
Seungjae Eom;Kenta Ozeki
一个图G的二分是将它的顶点集划分为基数相同的两个部分。G的AK-二等分是G的一个二等分，使得每个部分的每个分支至多有k个顶点。Cui和Liu证明了每一个无爪三次图都含有一个2-二等分图。本文改进了这一结果，证明了每个无爪三次图都包含一个具有有限条单色边的2-二等分图，其中2-二等分图的单色边是连接2-二等分图同一部分的两个顶点的边.我们还证明了我们的界是最好的可能为所有的无爪三次简单图。
A bisection of a graphGis a partition of its vertex set into two parts of the same cardinality. Ak-bisection ofGis a bisection ofGsuch that every component of each part has at mostkvertices. Cui and Liu proved that every claw-free cubic graph contains a 2-bisection. In this paper, we improve this result showing that every claw-free cubic graph contains a 2-bisection with bounded number of monochromatic edges, where amonochromatic edgeof a 2-bisection is an edge connecting two vertices of the same part of the 2-bisection. We also prove that our bound is best possible for all claw-free cubic simple graphs.
影响因子：
0.9
作者：
M. Abreu;Jan Goedgebeur;D. Labbate;G. Mazzuoccolo
通讯作者：
G. Mazzuoccolo
关于无爪三次图二等分的一个注记
DOI：
10.1016/j.dam.2018.03.016
发表时间：
2017
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
M. Abreu;Jan Goedgebeur;D. Labbate;G. Mazzuoccolo
通讯作者：
G. Mazzuoccolo