Generating bricks

• Autores: Serguei Norine, Robin Thomas
• Localización: Journal of combinatorial theory. Series B, ISSN 0095-8956, Vol. 97, Nº. 5, 2007, págs. 769-817
• Idioma: inglés
• DOI: 10.1016/j.jctb.2007.01.002
• Texto completo no disponible (Saber más ...)
• Resumen

  • A brick is a 3-connected graph such that the graph obtained from it by deleting any two distinct vertices has a perfect matching. The importance of bricks stems from the fact that they are building blocks of the matching decomposition procedure of Kotzig, and Lovász and Plummer. We prove a "splitter theorem" for bricks. More precisely, we show that if a brick H is a "matching minor" of a brick G, then, except for a few well-described exceptions, a graph isomorphic to H can be obtained from G by repeatedly applying a certain operation in such a way that all the intermediate graphs are bricks and have no parallel edges. The operation is as follows: first delete an edge, and for every vertex of degree two that results contract both edges incident with it. This strengthens a recent result of de Carvalho, Lucchesi and Murty.