A note on 2-bisections of claw-free cubic graphs
A note on 2-bisections of claw-free cubic graphs
复制标题
关于无爪三次图二等分的一个注记
DOI：
10.1016/j.dam.2018.03.016
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
G. Mazzuoccolo
中科院分区：
文献类型：
--
作者：
M. Abreu;Jan Goedgebeur;D. Labbate;G. Mazzuoccolo
无桥三次图G的k等分是其顶点集的2着色，使得颜色类具有相同的基数，并且由颜色类诱导的两个子图中所有连通分量的阶数最多为k。Ban和Linial推测除Petersen图外，每个无桥三次图都允许2等分。本文证明了无爪三次图的Ban-Linial猜想。
A k-bisection of a bridgeless cubic graph G is a 2-colouring of its vertex set such that the colour classes have the same cardinality and all connected components in the two subgraphs induced by the colour classes have order at most k. Ban and Linial conjectured that every bridgeless cubic graph admits a 2-bisection except for the Petersen graph. In this note, we prove Ban–Linial’s conjecture for claw-free cubic graphs.