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 R.. - In: JOURNAL OF ALGORITHMS. - ISSN 0196-6774. - STAMPA. - 32:1(1999), pp. 1-15.
Titolo: | Indecomposable r-graphs and some other counterexamples |
Autori: | |
Data di pubblicazione: | 1999 |
Rivista: | |
Citazione: | Indecomposable r-graphs and some other counterexamples / Rizzi R.. - In: JOURNAL OF ALGORITHMS. - ISSN 0196-6774. - STAMPA. - 32:1(1999), pp. 1-15. |
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. |
Handle: | http://hdl.handle.net/11562/409601 |
Appare nelle tipologie: | 01.01 Articolo in Rivista |