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 to be indecomposable when its edge set E cannot be partitioned as E = E1 ∪ E2 so that Gi (V, Ei ) is an ri-graph for i = 1, 2 and, for some r1 , r2 . We give an indecomposable r-graph for every integer r ≥ 4. This answers a question raised in [Seymour, Proc London Math Soc 38 (1979, 423–460], and has interesting consequences for the Schrijver System of the T-cut polyhedron to be given in [Rizzi, 1997, to appear]. 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 that "being indecomposable" does not imply "being poorly matchable." Next we give a poorly matchable r-graph for every r ≥ 4. The article provides counterexamples to some conjectures of Seymour.

Indecomposable r-graphs and some other counterexamples

RIZZI, ROMEO
1999-01-01

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 to be indecomposable when its edge set E cannot be partitioned as E = E1 ∪ E2 so that Gi (V, Ei ) is an ri-graph for i = 1, 2 and, for some r1 , r2 . We give an indecomposable r-graph for every integer r ≥ 4. This answers a question raised in [Seymour, Proc London Math Soc 38 (1979, 423–460], and has interesting consequences for the Schrijver System of the T-cut polyhedron to be given in [Rizzi, 1997, to appear]. 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 that "being indecomposable" does not imply "being poorly matchable." Next we give a poorly matchable r-graph for every r ≥ 4. The article provides counterexamples to some conjectures of Seymour.
1999
r-graph; indecomposable; Petersen graph; Fulkerson coloring
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/409601
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 12
social impact