Premium
Generating simple near‐bipartite bricks
Author(s) -
Kothari Nishad,
Carvalho Marcelo H.
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22579
Subject(s) - bipartite graph , combinatorics , mathematics , brick , complete bipartite graph , matching (statistics) , vertex (graph theory) , simple (philosophy) , class (philosophy) , discrete mathematics , graph , computer science , philosophy , statistics , archaeology , epistemology , history , artificial intelligence
Abstract A brick is a 3‐connected graph such that the graph obtained from it by deleting any two distinct vertices has a perfect matching. A brick G is near ‐ bipartite if it has a pair of edges α and β such that G − { α , β } is bipartite and matching covered; examples are K 4 and the triangular prismC 6 ¯ . The significance of near‐bipartite bricks arises from the theory of ear decompositions of matching covered graphs. The object of this paper is to establish a generation procedure which is specific to the class of simple near‐bipartite bricks. In particular, we prove that every simple near‐bipartite brick G has an edge e such that the graph obtained from G − e by contracting each edge that is incident with a vertex of degree two is also a simple near‐bipartite brick, unless G belongs to any of eight well‐defined infinite families. This is a refinement of the brick generation theorem of Norine and Thomas which is applicable to the class of near‐bipartite bricks. Earlier, the first author proved a similar generation theorem for (not necessarily simple) near‐bipartite bricks; we deduce our main result from this theorem. Our proof is based on a strategy of Carvalho, Lucchesi and Murty and uses several of their techniques and results.