Indecomposabler-graphs and some other counterexamples

✍ Scribed by Rizzi, Romeo

• Publisher: John Wiley and Sons
• Year: 1999
• Tongue: English
• Weight: 260 KB
• Volume: 32
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199909)32:1<1::aid-jgt1>3.0.co;2-b

✦ Synopsis

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 = E 1 ∪ E 2 so that G i (V, E i ) is an r igraph 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 [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.