Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

On odd and semi-odd linear partitions of cubic graphs

100%

Fouquet J.-L., Thuillier H., Vanherpe J.-M., Wojda A.

Discussiones Mathematicae Graph Theory

2009

tom 29

nr 2

275-292

A linear forest is a graph whose connected components are chordless paths. A linear partition of a graph G is a partition of its edge set into linear forests and la(G) is the minimum number of linear forests in a linear partition. In this paper we consider linear partitions of cubic simple graphs for which it is well known that la(G) = 2. A linear partition $L = (L_B,L_R)$ is said to be odd whenever each path of $L_B ∪ L_R$ has odd length and semi-odd whenever each path of $L_B$ (or each path of $L_R$) has odd length. In [2] Aldred and Wormald showed that a cubic graph G is 3-edge colourable if and only if G has an odd linear partition. We give here more precise results and we study moreover relationships between semi-odd linear partitions and perfect matchings.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Fouquet J.-L.

1 Thuillier H.

1 Vanherpe J.-M.

1 Wojda A.

1 2009

Wyniki wyszukiwania

On odd and semi-odd linear partitions of cubic graphs