On odd and semi-odd linear partitions of cubic graphs

• Autorzy: Jean-Luc Fouquet , Henri Thuillier , Jean-Marie Vanherpe , Adam P. Wojda
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

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

Kategorie tematyczne

• 05C70: Factorization, matching, partitioning, covering and packing
• 05C38: Paths and cycles

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2009
• Tom: 29
• Numer: 2
• Strony: 275-292

Daty

wydano

2009

otrzymano

2007-12-03

poprawiono

2008-06-13

zaakceptowano

2008-06-13

Twórcy

autor

Jean-Luc Fouquet

• L.I.F.O., Faculté des Sciences, B.P. 6759, Université d'Orléans, 45067 Orléans Cedex 2, France

autor

Henri Thuillier

• L.I.F.O., Faculté des Sciences, B.P. 6759, Université d'Orléans, 45067 Orléans Cedex 2, France

autor

Jean-Marie Vanherpe

• L.I.F.O., Faculté des Sciences, B.P. 6759, Université d'Orléans, 45067 Orléans Cedex 2, France

autor

Adam P. Wojda

• Wydział Matematyki Stosowanej, Zakład Matematyki Dyskretnej, AGH, Al. Mickiewicza 30, 30-059 Kraków, Poland

Bibliografia

• [1] J. Akiyama, G. Exoo and F. Harary, Covering and packing in graphs III, Cyclic and Acyclic Invariant, Math. Slovaca 30 (1980) 405-417.
• [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.
• [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.
• [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.
• [5] M. Habib and B. Peroche, La k-arboricité linéaire des arbres, Annals of Discrete Math. 17 (1983) 307-317.
• [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.
• [7] I. Holyer, The NP-completeness of edge coloring, SIAM J. Comput. 10 (1981) 718-720, doi: 10.1137/0210055.
• [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.

Identyfikatory

DOI

10.7151/dmgt.1447