pith. sign in

arxiv: 1707.04452 · v1 · pith:VASX5LVMnew · submitted 2017-07-14 · 🧮 math.CO

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

classification 🧮 math.CO
keywords cubicgraphbisectionbridgelessclassesclaw--freecolourgraphs
0
0 comments X
read the original abstract

A \emph{$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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.