Displaying similar documents to “A note on line colorings of cubic graphs”

Path and cycle factors of cubic bipartite graphs

M. Kano, Changwoo Lee, Kazuhiro Suzuki (2008)

Discussiones Mathematicae Graph Theory

Similarity:

For a set S of connected graphs, a spanning subgraph F of a graph is called an S-factor if every component of F is isomorphic to a member of S. It was recently shown that every 2-connected cubic graph has a {Cₙ | n ≥ 4}-factor and a {Pₙ | n ≥ 6}-factor, where Cₙ and Pₙ denote the cycle and the path of order n, respectively (Kawarabayashi et al., J. Graph Theory, Vol. 39 (2002) 188-193). In this paper, we show that every connected cubic bipartite graph has a {Cₙ | n ≥ 6}-factor, and has...

Mácajová and Škoviera conjecture on cubic graphs

Jean-Luc Fouquet, Jean-Marie Vanherpe (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A conjecture of Mácajová and Skoviera asserts that every bridgeless cubic graph has two perfect matchings whose intersection does not contain any odd edge cut. We prove this conjecture for graphs with few vertices and we give a stronger result for traceable graphs.