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

Abstract

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

How to cite

top

Jean-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. [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. [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. [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. [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. [5] M. Habib and B. Peroche, La k-arboricité linéaire des arbres, Annals of Discrete Math. 17 (1983) 307-317. Zbl0523.05025
  6. [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. [7] I. Holyer, The NP-completeness of edge coloring, SIAM J. Comput. 10 (1981) 718-720, doi: 10.1137/0210055. Zbl0473.68034
  8. [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. [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. [10] V.G. Vizing, On an estimate of the chromatic class of p-graph, Diskrete Analiz 3 (1964) 25-30. 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.