# On odd and semi-odd linear partitions of cubic graphs

Jean-Luc Fouquet; Henri Thuillier; Jean-Marie Vanherpe; Adam P. Wojda

Discussiones Mathematicae Graph Theory (2009)

- Volume: 29, Issue: 2, page 275-292
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topJean-Luc Fouquet, et al. "On odd and semi-odd linear partitions of cubic graphs." Discussiones Mathematicae Graph Theory 29.2 (2009): 275-292. <http://eudml.org/doc/270469>.

@article{Jean2009,

abstract = {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.},

author = {Jean-Luc Fouquet, Henri Thuillier, Jean-Marie Vanherpe, Adam P. Wojda},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {Cubic graph; linear arboricity; strong matching; edge-colouring; cubic graph},

language = {eng},

number = {2},

pages = {275-292},

title = {On odd and semi-odd linear partitions of cubic graphs},

url = {http://eudml.org/doc/270469},

volume = {29},

year = {2009},

}

TY - JOUR

AU - Jean-Luc Fouquet

AU - Henri Thuillier

AU - Jean-Marie Vanherpe

AU - Adam P. Wojda

TI - On odd and semi-odd linear partitions of cubic graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2009

VL - 29

IS - 2

SP - 275

EP - 292

AB - 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.

LA - eng

KW - Cubic graph; linear arboricity; strong matching; edge-colouring; cubic graph

UR - http://eudml.org/doc/270469

ER -

## References

top- [1] J. Akiyama, G. Exoo and F. Harary, Covering and packing in graphs III, Cyclic and Acyclic Invariant, Math. Slovaca 30 (1980) 405-417. Zbl0458.05050
- [2] R.E.L. Aldred and N.C. Wormald, More on the linear k-arboricity of regular graphs, Australas. J. Combin. 18 (1998) 97-104. Zbl0930.05075
- [3] J.C. Bermond, J.L. Fouquet, M. Habib and B. Peroche, On linear k-arboricity, Discrete Math. 52 (1984) 123-132, doi: 10.1016/0012-365X(84)90075-X. Zbl0556.05054
- [4] J.A. Bondy, Balanced colourings and the four color conjecture, Proc. Am. Math. Soc. 33 (1972) 241-244, doi: 10.1090/S0002-9939-1972-0294173-4. Zbl0238.05107
- [5] M. Habib and B. Peroche, La k-arboricité linéaire des arbres, Annals of Discrete Math. 17 (1983) 307-317. Zbl0523.05025
- [6] F. Harary, Covering and Packing in graphs I, Ann. New York Acad. Sci. 175 (1970) 198-205, doi: 10.1111/j.1749-6632.1970.tb56470.x. Zbl0226.05119
- [7] I. Holyer, The NP-completeness of edge coloring, SIAM J. Comput. 10 (1981) 718-720, doi: 10.1137/0210055. Zbl0473.68034
- [8] F. Jaeger, Etude de quelques invariants et problèmes d'existence en théorie des graphes, Thèse d'Etat, IMAG Grenoble, 1976. Proc 10th Ann. Symp. on Theory of Computing (1978) 216-226.
- [9] C. Thomassen, Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5, J. Combin. Theory (B) 75 (1999) 100-109, doi: 10.1006/jctb.1998.1868.
- [10] V.G. Vizing, On an estimate of the chromatic class of p-graph, Diskrete Analiz 3 (1964) 25-30.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.