Generating near‐bipartite bricks
Nishad Kothari · Journal of Graph Theory · 2018
Abstract Carvalho, Lucchesi and Murty (2006, How to build a brick, Discrete Math., 306, 2383‐2410) gave a generation procedure for bricks. In particular, they showed that every brick may be constructed from , the triangular prism , and the Petersen graph. The object of this paper is to establish a generation procedure that is specific to the class of near‐bipartite bricks. In particular, we show that every near‐bipartite brick may be constructed from and so that each intermediate brick is also near‐bipartite. Norine and Thomas (2007, Generating bricks, J. Combin. Theory Ser. B, 97, 769‐817) proved a generation theorem for simple bricks. In a subsequent work with Marcelo H. de Carvalho (2017, Generating simple near‐bipartite bricks, https://arxiv.org/abs/1704.08796 ), we use the results of this paper to prove a generation theorem for simple near‐bipartite bricks.