A note on 2-bisections of claw-free cubic graphs

作者：Abreu Marien; Goedgebeur Jan; Labbate Domenico^*; Mazzuoccolo Giuseppe

来源：Discrete Applied Mathematics, 2018, 244: 214-217.

DOI：10.1016/j.dam.2018.03.016

• Colouring
• Bisection
• Claw-free graph
• Cubic graph

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.

• 出版日期2018-7-31