2018/03/23 by Kothari, Nishad, de Carvalho, Marcelo H., Lucchesi, Cláudio L. +1 · 3 citations
#05C40 #05C70 #05C75 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1803.08713
Lovász (1987) proved that every matching covered graph G may be uniquely decomposed into a list of bricks (nonbipartite) and braces (bipartite); we let b(G) denote the number of bricks. An edge e is removable if G-e is also matching covered; furthermore, e is b-invariant if b(G-e)=1, and e is quasi-b-invariant if b(G-e)=2. (Each edge of the Petersen graph is quasi-b-invariant.) A brick G is near-bipartite if it has a pair of edges \e,f\ so that G-e-f is matching covered and bipartite; such a pair \e,f\ is a removable doubleton. (Each of K4 and the triangular prism C6 has three removable doubletons.) Carvalho, Lucchesi and Murty (2002) proved a conjecture of Lovász which states that every brick, distinct from K4, C6 and the Petersen graph, has a b-invariant edge. A cubic graph is essentially 4-edge-connected if it is 2-edge-connected and if its only 3-cuts are the trivial ones; it is well-known that each such graph is either a brick or a brace; we provide a graph-theoretical proof of this fact. We prove that if G is any essentially 4-edge-connected cubic brick then its edge-set may be partitioned into three (possibly empty) sets: (i) edges that participate in a removable doubleton, (ii) b-invariant edges, and (iii) quasi-b-invariant edges; our Main Theorem states that if G has two adjacent quasi-b-invariant edges, say e1 and e2, then either G is the Petersen graph or the (near-bipartite) Cubeplex graph, or otherwise, each edge of G (distinct from e1 and e2) is b-invariant. As a corollary, we deduce that each essentially 4-edge-connected cubic non-near-bipartite brick G, distinct from the Petersen graph, has at least |V(G)| b-invariant edges.