Henri THUILLER

(LIFO, Francja)

On semi-odd linear partitions of cubic graphs

A linear forest is a graph in which each connected component is a chordless path. 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. For a cubic graph $G$ it is known that $la(G)=2$. A linear partition $L = (L_1, L_2)$ is said to be semi-odd whenever each component of $L_1$ (or each component of $L_2$) has odd length. We study relationschips between semi-odd linear partitions and perfect matchings.

Serdecznie zapraszamy wszystkich chêtnych !