A -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.
A note on 2--bisections of claw--free cubic graphs.
ABREU, Marien;LABBATE, Domenico;
2018-01-01
Abstract
A -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.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
2bisectionsofclawfreegraphs_final.pdf
accesso aperto
Descrizione: Versione accettata
Tipologia:
Documento in Post-print
Licenza:
Dominio pubblico
Dimensione
217.92 kB
Formato
Adobe PDF
|
217.92 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
