Premium
K 4 ‐free and C 6 ¯ ‐free Planar Matching Covered Graphs
Author(s) -
Kothari Nishad,
Murty U. S. R.
Publication year - 2016
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.21882
Subject(s) - combinatorics , mathematics , planar graph , matching (statistics) , subdivision , graph , induced subgraph , factor critical graph , conformal map , line graph , discrete mathematics , graph power , vertex (graph theory) , geometry , history , statistics , archaeology
A bi‐subdivision of a graph J is a graph H obtained from J by subdividing each of its edges by inserting an even number of vertices. A matching covered subgraph H of a matching covered graph G is conformal if G − V ( H ) has a perfect matching. Using the theory of ear decompositions, Lovász (Combinatorica, 3 (1983), 105–117) showed that every nonbipartite matching covered graph has a conformal subgraph which is either a bi‐subdivision of K 4 or ofC 6 ¯ . (The graphC 6 ¯ is the triangular prism.) A matching covered graph is K 4 ‐ based if it contains a bi‐subdivision of K 4 as a conformal subgraph; otherwise it is K 4 ‐ free .C 6 ¯ ‐ based andC 6 ¯ ‐ free graphs are analogously defined. The result of Lovász quoted above implies that any nonbipartite matching covered graph is either K 4 ‐based orC 6 ¯ ‐based (or both). The problem of deciding which matching covered graphs are K 4 ‐based and which areC 6 ¯ ‐based is, in general, unsolved. In this paper, we present a solution to this classification problem in the special case of planar graphs. In Section 2, we show that a matching covered graph is K 4 ‐free ( C 6 ¯ ‐free) if and only if each of its bricks is K 4 ‐free ( C 6 ¯ ‐free). In Section 5, we show that a planar brick is K 4 ‐free if and only if it has precisely two odd faces. In Section 6, we determine the list of allC 6 ¯ ‐free planar bricks; apart from one exception, it consists of two infinite families of bricks. The principal tool we use for proving our results is the brick generation procedure established by Norine and Thomas (J Combin Theory Ser B, 97 (2007), 769–817).