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

2017/07/14 by M. Abreu, Abreu, M., Jan Goedgebeur +5 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1707.04452

openalex publication_date 2017/07/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 \em 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.

Cited by

• On the Ban-Linial Conjecture

Related

• On 2-bisections and monochromatic edges in claw-free cubic multigraphs
• Colourings of cubic graphs inducing isomorphic monochromatic subgraphs
• Claw-free cubic graphs are (1, 1, 2, 2)-colorable
• Diamond-free, claw-free cubic graphs are (1, 1, 2, 3)-packing colorable
• Hoffmann-Ostenhof's conjecture for claw-free cubic graphs