An r-graph is any graph that can be obtained as a conic combination of its own 1-factors. An r-graph G=(V,E) is said indecomposable when its edge set E cannot be partitioned as the disjoint union of sets E_1 and E_2 so that (V,E_i) is an r_i-graph for i=1,2 and for some r_1, r_2. We give an indecomposable r-graph for every integer r &gt;= 4. This answers a question raised in 1: [ P.D. Seymour, On multi-colourings of cubic graphs, and conjectures of Fulkerson and Tutte. Proceedings of the London Mathematical Society, Vol. 38, 423--460, (1979)] and 2: [ P.D. Seymour, Some unsolved problems on one-factorizations of graphs. Graph Theory and Related Topics, J.A. Bondy and U.S.R. Murty, Eds., 367--368, Academic Press, New York, 1979] and has interesting consequences for the Schrijver System of the T-cut polyhedron to be given in 3: [ R. Rizzi, Minimum T-cuts and optimal T-pairings, Discrete Mathematics, 2002]. A graph in which every two 1-factors intersect is said to be poorly matchable. Every poorly matchable r-graph is indecomposable. We show that for every r &gt;= 4 being indecomposable" does not imply "being poorly matchable". Next we give a poorly matchable r-graph for every r &gt;= 4. The paper provides counterexamples to some conjectures of Seymour first appeared in  and ."

Indecomposable r-graphs and some other counterexamples / Rizzi, Romeo. - ELETTRONICO. - (1999), pp. 1-14.

### Indecomposable r-graphs and some other counterexamples

#### Abstract

An r-graph is any graph that can be obtained as a conic combination of its own 1-factors. An r-graph G=(V,E) is said indecomposable when its edge set E cannot be partitioned as the disjoint union of sets E_1 and E_2 so that (V,E_i) is an r_i-graph for i=1,2 and for some r_1, r_2. We give an indecomposable r-graph for every integer r >= 4. This answers a question raised in 1: [ P.D. Seymour, On multi-colourings of cubic graphs, and conjectures of Fulkerson and Tutte. Proceedings of the London Mathematical Society, Vol. 38, 423--460, (1979)] and 2: [ P.D. Seymour, Some unsolved problems on one-factorizations of graphs. Graph Theory and Related Topics, J.A. Bondy and U.S.R. Murty, Eds., 367--368, Academic Press, New York, 1979] and has interesting consequences for the Schrijver System of the T-cut polyhedron to be given in 3: [ R. Rizzi, Minimum T-cuts and optimal T-pairings, Discrete Mathematics, 2002]. A graph in which every two 1-factors intersect is said to be poorly matchable. Every poorly matchable r-graph is indecomposable. We show that for every r >= 4 being indecomposable" does not imply "being poorly matchable". Next we give a poorly matchable r-graph for every r >= 4. The paper provides counterexamples to some conjectures of Seymour first appeared in  and ."
##### Scheda breve Scheda completa Scheda completa (DC)
1999
Trento, Italia
Università degli Studi di Trento. DEPARTMENT OF INFORMATION AND COMMUNICATION TECHNOLOGY
Indecomposable r-graphs and some other counterexamples / Rizzi, Romeo. - ELETTRONICO. - (1999), pp. 1-14.
Rizzi, Romeo
File in questo prodotto:
File
tec52.pdf

accesso aperto

Tipologia: Versione editoriale (Publisher’s layout)
Dimensione 353.38 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11572/358470`
• ND
• ND
• ND