Quasimonotone Graphs

Abstract

For any class $\mathcal {C}$ of bipartite graphs, we define quasi-$\mathcal {C}$ to be the class of all graphs G such that every bipartition of G belongs to $\mathcal {C}$. This definition is motivated by a generalisation of the switch Markov chain on perfect matchings from bipartite graphs to nonbipartite graphs. The monotone graphs, also known as bipartite permutation graphs and proper interval bigraphs, are such a class of bipartite graphs. We investigate the structure of quasi-monotone graphs and hence construct a polynomial time recognition algorithm for graphs in this class.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

In [5] (with Jerrum) and [6] we considered the switch Markov chain on perfect matchings in bipartite and nonbipartite graphs. This chain repeatedly replaces two matching edges with two non-matching edges involving the same four vertices. We considered the ergodicity and mixing properties of the chain.

In particular, we proved in [5] that the chain is rapidly mixing (i.e. converges in polynomial time) on the class of monotone graphs. This class of bipartite graphs was defined by Diaconis, Graham and Holmes in [4], motivated by statistical applications of perfect matchings. The biadjacency matrices of graphs in the class have a “staircase” structure. Diaconis et al. conjectured the rapid mixing property shown in [5]. We also showed in [5] that this class is, in fact, identical to the known class of bipartite permutation graphs [14], which is itself known to be identical to the class of proper interval bigraphs [9].

In extending the work of [5] to nonbipartite graphs in [6], we showed that the rapid mixing proof for monotone graphs extends easily to a class of graphs which includes, beside the monotone graphs themselves, all proper, or unit, interval graphs [1]. In this class the bipartite graph given by the cut between any bipartition of the vertices of the graph must be a monotone graph. We called these graphs quasimonotone.

In fact, “quasi-” is an operator on bipartite graph classes, and can be applied more generally. In this view, quasimonotone graphs are quasi-monotone graphs, as formally defined in Sect. 2, and discussed in Sect. 2.1, below. For any class of bipartite graphs that is recognisable in polynomial time, the definition of its quasi-class implies membership in co-$\mathbb {NP}$. Thus an immediate question is whether we can recognise the quasi-class in polynomial time. The main contribution of this paper is a polynomial time recognition algorithm for quasimonotone graphs.

1.1 Definitions and Notation

If $G=(V,E)$ is a graph and $U\subseteq V$, then G[U] is the subgraph induced by U. Often we do not distinguish between the set U and the subgraph it induces. So a cycle in G is either a subgraph or the set of its vertices. Similarly, we will write $G=H$ when G is isomorphic to H. A subgraph of G is a cycle in G if it is connected and 2-regular. The length or size of a cycle is the number of its edges (or vertices). A chord of a cycle (U, F) in G is an edge in $U^{(2)} \cap E \setminus F$. A chord in a cycle of even length is odd if the distance between its endpoints on the cycle is odd. That is, an odd chord splits an even cycle into two cycles of even length. An even chord splits an even cycle into two cycles of odd length.

A hole in a graph is a chordless cycle of length at least five. A cycle of length three is a triangle, and a cycle of length four a quadrangle. A hole is odd if it has an odd number of vertices, otherwise even. Let $\textsc {HoleFree}$ be the class of graphs without a hole, and $\textsc {EvenHoleFree}$ the class of graphs without even holes. A long hole is an odd hole of size at least 7.

For a graph $G=(V,E)$, $L \subseteq V$ and $R = V \setminus L$ the graph $G[L{:}R]$ is the bipartite graph with bipartition L, R, and edge set the cut $L{:}R= \{xy\in E : x\in L, y\in R\}$. We refer to $G[L{:}R$] as a bipartition of G.

The distance ${\text {dist}}(u,v)$ between two vertices u and v is the length of a shortest $(u,\ldots , v)$ path in G. For vertices x and y in a subgraph H of G we denote their distance in H by ${\text {dist}}_H(x,y)$. If $v\in V$, ${\text {dist}}(v,H)$ is the smallest distance ${\text {dist}}(v,w)$ from v to any vertex $w\in H$. The maximum distance between two vertices in G is the diameter of G. The neighbourhood of a vertex v is N(v).

1.2 Structure of the Paper

In 2 we discuss quasi-classes and give examples in Sect. 2.1. Sections 3 to 6 show that quasimonotone graphs can be recognised in polynomial time. In Sect. 3.1 we prove some properties of quasimonotone graphs, using their characterisation by forbidden induced subgraphs. The anticipated recognition algorithm first looks for flaws (defined in Sect. 3.1) and then branches into different procedures depending on the length of a short hole (defined in Sect. 3.3) in the input graph. The remaining forbidden subgraphs are preholes, also defined in Sect. 3.1.

Sections 4 and 5 deal with graphs containing a long hole. We start with lemmas showing that the long hole enforces an annular structure in the absence of flaws. The structure is determined by splitting, described in Sect. 5.1. Possible preholes must wind round this annulus once or twice. We complete the process by checking for preholes, using a procedure given in Sect. 5.2. The remaining cases where no long hole exists are considered in Sect. 6. Finally Sect. 7 concludes the paper.

A more detailed version (also with more examples) is available, see [7].

2 Quasi-classes and Pre-graphs

A hereditary class of graphs is closed under induced subgraphs. Let $\textsc {Bipartite}$ denote the class of bipartite graphs, and let $\mathcal {C}\subseteq \textsc {Bipartite}$. Then we will say that the graph G is quasi-$\mathcal {C}$ if $G[L{:}R]\in \mathcal {C}$ for all bipartitions L, R of V.

Lemma 1

If $\mathcal {C}\subseteq \textsc {Bipartite}$ is a hereditary class that is closed under disjoint union then $\mathcal {C}= \textsc {Bipartite} \cap {\text {quasi-}}\mathcal {C}$.

Proof

First let $G = (L \cup R,E)$ be any bipartite graph that does not belong to $\mathcal {C}$. Since $G = G[L{:}R]$ the graph G does not belong to quasi-$\mathcal {C}$. Hence $\mathcal {C}\supseteq \textsc {Bipartite} \cap {\text {quasi-}}\mathcal {C}$.

Next we show $\mathcal {C}\subseteq \textsc {Bipartite} \cap {\text {quasi-}}\mathcal {C}$. Let $G = (X \cup Y,E)$ be a graph in $\mathcal {C}$ and let $L{:}R$ be a bipartition of $X \cup Y$. Now $G[L{:}R]$ is the disjoint union of $G_1 = G[(X \cap L)\cup (Y \cap R)]$ and $G_2 = G[(X \cap R)\cup (Y \cap L)]$. The graphs $G_1$ and $G_2$ belong to $\mathcal {C}$ since the class is hereditary, and hence $G[L{:}R]$ is in $\mathcal {C}$ because $\mathcal {C}$ is closed under disjoint union. Thus $G \in {\text {quasi-}}\mathcal {C}$.    $\square$

A hereditary graph class can equally well be characterised by a set $\mathcal {F}$ of forbidden subgraphs. The set $\mathcal {F}$ is minimal if no graph in $\mathcal {F}$ contains any other as an induced subgraph. For a bipartite graph H, a graph $G=(V,E)$ is a pre-H if there is a bipartition L, R of V such that $G[L{:}R]=H$. In this case H is a spanning subgraph of G. Clearly any bipartite graph H is itself a pre-H.

Lemma 2

If $\mathcal {C}\subseteq \textsc {Bipartite}$ is characterised by a set $\mathcal {F}$ of forbidden induced subgraphs, let pre-$\mathcal {F}= \{\text {pre-}H \mid H \in \mathcal {F}\}$. Then quasi-$\mathcal {C}$ is characterised by the set of forbidden induced subgraphs pre-$\mathcal {F}$.

Proof

Suppose $G=(V,E)$ contains $H'=(V',E')$, a pre-H for some $H\in \mathcal {F}$. Then $V'$ has a bipartition $L',R'$ such that $H'[L'$:$R']=H$. Extending $L',R'$ to a bipartition L, R of V, $G[L{:}R]$ contains H. Then $G[L{:}R]\notin \mathcal {C}$, so $G\,\notin \,{\text {quasi-}}\mathcal {C}$. Conversely, if $G\,\in \,{\text {quasi-}}\mathcal {C}$, every $G[L{:}R]\in \mathcal {C}$, so no $G[L{:}R]$ contains H, for any $H\in \mathcal {F}$. Thus G contains no pre-H, for any $H\in \mathcal {F}$, that is, no $H'\in \text {pre-}\mathcal {F}$.    $\square$

2.1 Examples

The class quasi-$\textsc {Bipartite}$ is clearly the set of all graphs.

If $\mathcal {C}$ is the class of complete bipartite graphs, it is easy to see that quasi-$\mathcal {C}$ is the class of complete graphs. Note however, that this class is not closed under disjoint union. Now, if $\mathcal {C}$ becomes the class of graphs for which every component is complete bipartite, then quasi-$\mathcal {C}$ is the class of graphs without $P_4$, paw or diamond. These three graphs are the pre-$P_4$’s, see Fig. 1.

Fig. 1.

The pre-$P_4$’s: the path $P_4$, the paw and the diamond

If $\mathcal {C}_d$ is the class of bipartite graphs with degree at most d, for a fixed integer $d>0$, then quasi-$\mathcal {C}_d$ is the class of all graphs with degree at most d. The unique forbidden subgraph for $\mathcal {C}_d$ is clearly the star $K_{1,d+1}$. Therefore, the class quasi-$\mathcal {C}_d$ is characterised by forbidding pre-$K_{1,d+1}$’s, a set with size $O(d^2)$. Hence quasi-$\mathcal {C}_d$ can be recognised in polynomial time, for fixed d.

A less obvious example is for the class $\mathcal {C}$ of linear forests, which are disjoint unions of paths. Its quasi-class contains all graphs with connected components that are either a path or an odd cycle.

ChordalBipartite is the class of hole-free bipartite graphs. OddChordal is the class of graphs in which every even cycle of length at least six has an odd chord. We show in [6] that quasi-$\textsc {ChordalBipartite} =\textsc {OddChordal}$. The complexity of the recognition problem for the class OddChordal is open, even though ChordalBipartite can be recognised in almost linear time [12].

3 The Structure of Quasimonotone Graphs

3.1 Flaws and Preholes

A bipartite graph is monotone if and only if the rows and columns of its biadjacency matrix can be permuted such that the ones appear consecutively and the boundaries of these intervals are monotonic functions of the row or column index. That is, all the ones are in a staircase-shaped region in the biadjacency matrix. A bipartite graph is monotone if and only if it does not contain a hole, tripod, stirrer or armchair as induced subgraph, see Fig. 2 and [11] Lemma 1.46 on page 52 or [2] Proposition 6.2.1 on page 93. Monotone graphs are also called bipartite permutation graphs [14] and proper interval bigraphs [9].

Fig. 2.

The tripod, the stirrer and the armchair.

Let Monotone denote the class of monotone graphs, then the Quasimonotone will denote the class quasi-Monotone. Two example graphs are shown in Fig. 3. Let $\textsc {Flaw}$ be the class containing all pre-tripods, pre-stirrers and pre-armchairs. We will say that any graph in $\textsc {Flaw}$ is a flaw. A flawless graph G will be one which contains no flaw as an induced subgraph. Since all flaws have seven vertices, we can test in $O(n^7)$ time whether an input graph G on n vertices is flawless. Let $\textsc {Flawless}$ denote the class of flawless graphs, and let $\textsc {Quasimonotone}$ be the class of quasimonotone graphs.

Fig. 3.

Two quasimonotone graphs

Let $P=(p_1,p_2,\dots ,p_\ell )$ be a path or even cycle in G. The alternating bipartition L, R of P assigns $L=\{p_1,p_3,\ldots \}$ and $R=\{p_2,p_4,\ldots \}$. The path P is prechordless if it is an induced path $G[L{:}R]$. Similarly, let $C=(p_1,p_2,\ldots ,p_\ell )$ be an even cycle in G. Then C is a prehole if it is a hole in $G[L{:}R]$. Thus C must be an even cycle, and all chords must run between L and L or R and R in an alternating bipartition L, R of C. This is equivalent to requiring that C has no odd chord. The alternating partition is inconsistent for an odd cycle, so an odd cycle C cannot be a prehole.

3.2 Properties of Flawless Graphs

Lemma 3

Let $G\in \textsc {Flawless}$. Let $P=(p_1,p_2,p_3,p_4,p_5,p_6,p_7)$ be a prechordless path in G, $(p_2,p_3,p_4,p_5,p_6)$ be a hole in G, or $(p_1,p_2,p_3,p_4,p_5,p_6)$ be a prehole in G. If $v\notin P$ is such that ${\text {dist}}(v,P)={\text {dist}}(v,p_4)$, then ${\text {dist}}(v,p_4)= 1$.

Lemma 4

Every hole or prehole in a connected flawless graph is dominating.

Proof

Let C be an odd hole or prehole in the connected flawless graph G. We show ${\text {dist}}(v,C)\le 1$ for every vertex v of G. If $v\in C$, this is obvious. Otherwise, let w be a vertex such that ${\text {dist}}(v,C)={\text {dist}}(v,w)$. Consider the subpath $P=(p_1,p_2,\ldots ,p_7)$ of C such that $w=p_4$, where this path wraps around C if $|C|<7$. Since C is a hole or a prehole, P is prechordless. The result then follows from Lemma 3.    $\square$

If C is an odd hole we will call $n(C)=\{v\in V:{\text {dist}}(v,C)\le 1\}$, the neighbourhood of C. If G is connected then $G=N(C)$ for any odd hole $C\subseteq G$.

Lemma 5

Suppose $G\in \textsc {Flawless} \cap \textsc {EvenHoleFree}$, and that C is an odd hole in G, of length at least seven. Then every vertex $v\in V$ has at most three neighbours in C. If there are two neighbours, w, x, then ${\text {dist}}_C(w,x)=2$. If there are three neighbours, w, x, y, then ${\text {dist}}_C(w,x)={\text {dist}}_C(x,y)=2$. If C is a short odd hole (see Sect. 3.3) in G, then v has at most two neighbours on C.

Lemma 6

Let C be a prehole in $G\in \textsc {Flawless}$. Then every vertex $v\in C$ has at most five neighbours in C. Two of these are via edges of C, so v is incident to at most three chords. If there are two chords, vw, vx, then ${\text {dist}}_C(w,x)=2$. If there are three chords, vw, vx, vy, then ${\text {dist}}_C(w,x)={\text {dist}}_C(x,y)=2$.

Proof

Otherwise, v must have at least four chords. These must be even chords to $c_0,c_2,c_4,c_6$, where $P=(c_0,c_1,\ldots ,c_6,c_7)$ is a subpath of C, since C is a prehole and G has no even holes. We now move v from L to R. The only new edges which appear in $G[L{:}R]$ are those adjacent to v. But now $c_0,v,c_3,c_4,c_5,c_6,c_7$ induce an armchair in $G[L{:}R]$, contradicting $G\in \textsc {Flawless}$, see Fig. 4.    $\square$

Fig. 4.

An armchair

The degree bound of Lemma 6 is tight, see Fig. 5.

Fig. 5.

A prehole with a vertex of degree 5

Lemma 7

Let C be an odd hole in $G\in \textsc {Flawless}$ such that $v\notin C$ and $x\notin C$ are adjacent. Then vertices $w,y\in C$ exist such that (v, x, y, w) is a quadrangle.

3.3 Determining a Short Odd Hole

We can test whether G contains a hole in time $O(|E|^2)$, using the algorithm of [13]. Moreover, the algorithm returns a hole if one exists. If the hole is even, we can conclude $G\notin \textsc {Quasimonotone}$. If $G\in \textsc {Flawless}$, we will show that it has a well-defined structure.

Lemma 8

If C is an odd cycle in a graph G, there is a triangle or an odd hole $C'$ in G.

Proof

The claim is clearly true if $|C|\le 3$. Otherwise, assume by induction that it is true for all cycles shorter than C. If C is not already a hole, it has a chord that divides it into a smaller odd cycle $C_1$, and an even cycle $C'_1$. The lemma now follows by induction on $C_1$.    $\square$

The proof of Lemma 8 can easily be turned into an efficient algorithm to find $C'$. An odd hole C is short if ${\text {dist}}(v,w)={\text {dist}}_C(v,w)$ for all pairs $v,w \in C$.

Lemma 9

If G is a triangle-free graph containing an odd hole C, then G contains a short odd hole.

Note that the proof of Lemma 9 gives an efficient algorithm for finding a short odd hole H, given any odd hole C. Clearly the shortest hole in G is a short hole, but the converse need not be true in general, even for quasimonotone graphs.

Fig. 6.

Short odd holes of unequal size in a quasimonotone graph.

Corollary 1

If G has a short odd hole C, ${\text {diam}}(G) \ge {\text {diam}}(C)=(|C|-1)/2$.

If C is a prehole, $G'=G[C]$, and $L{:}R$ is the alternating bipartition of C, then $G'[L{:}R]$ contains no edge other than those of C. A minimal prehole C is such that G[C] contains no prehole with fewer than |C| vertices.

4 Flawless Graphs Containing a Long Hole

4.1 Triangles

Lemma 10

Let G be a quasimonotone graph containing an odd hole C of size at least 7. Then G contains no triangle that has a vertex in C (Fig. 7).

Fig. 7.

In a quasimonotone graph a 5-hole and a triangle can share a vertex.

Lemma 11

Let G be a quasimonotone graph containing an odd hole C of size at least 7. Then G contains no triangle which is vertex-disjoint from C.

4.2 Long Odd Holes

Lemma 12

Let $C,C'$ be odd holes in a quasimonotone graph G such that $C'\cap C\ne \varnothing$, and $|C|,|C'|\ge 7$. Let $G'=G[(C'\cup C)\setminus (C'\cap C)]$, Then $G'$ has no odd hole or prehole.

Corollary 2

Let $C,C'$ be odd holes in a quasimonotone graph G, such that $C'\cap C\ne \varnothing$. Let $G'=G[(C'\cup C)\setminus (C'\cap C)]$. Then $G'$ is a monotone graph.

Note that the holes $C,C'$ in Corollary 2 can have different size. See Fig. 6, where $G'$ is a ladder (see [5]) with two pendant edges. However, if we have vertex-disjoint odd holes they cannot have different lengths.

A prism is the graph given by joining corresponding vertices in two cycles of the same length. It is an n-prism if the cycles have length n [10].

Lemma 13

Let G be a quasimonotone graph containing an odd hole C. Then G contains no vertex-disjoint hole $C'$ with $|C'|\ne |C|$. Moreover, if $|C|\ge 7$, any two vertex-disjoint holes with $|C'|=|C|$ induce a prism in G.

5 Preholes in Flawless Graphs

Lemma 14

If $G\in \textsc {Flawless}$ and has an odd hole of size $\ell \ge 7$, any minimal prehole C in G is either an even hole or (a) two odd holes intersecting in an edge or (b) two disjoint odd holes connected by a quadrangle. See Fig. 8.

Thus, if G contains an odd hole of size at least 7, minimal preholes have only two types, case (a) and case (b). From Lemma 13, case (b) are crossover preholes (Fig. 9).

Fig. 8.

Preholes with odd holes $C_1$, $C_2$, cases (a) left and (b) right.

Fig. 9.

Flawless crossover preholes.

So let us consider the case (a) preholes. We will call these Möbius preholes, since we will show that such a prehole must be a Möbius ladder [8, 10].

Lemma 15

Every Möbius prehole in a flawless graph is a Möbius ladder (Fig. 10).

Fig. 10.

Two different drawings of a Möbius ladder.

5.1 Splitting

Let G be a flawless graph with a hole C of length $|C|\ge 6$. If |C| is even, we conclude $G\notin \textsc {Quasimonotone}$, so $|C|\ge 7$ is odd. Thus G does not contain a triangle, from Lemmas 10 and 11. We will assume that this has been tested. We will now show that G must have the annular structure referred to in Sect. 1.2, rather like a monotone graph with its ends identified.

Now suppose G has a short odd hole C with $C\ge 7$, determined by the procedure of Lemma 9. Thus, by Corollary 1, ${\text {diam}}(G)\ge \tfrac{1}{2}(|C|-1)\ge 3$. Choose any $v\in C$, and consider the graph $G_v=G[V\setminus N[v]]$. Then $G_v$ contains no holes, since any hole H in $G_v$ must be a hole in G. But any hole H in G either contains v, or has a vertex w adjacent to v, by Lemma 4. Since $v,w\notin G_v$, $H\nsubseteq G_v$. Neither can $G_v$ contain a prehole, since any prehole must contain two holes. Thus $G_v$ is flawless and contains no holes or preholes, so is a monotone graph. Now ${\text {diam}}(G)$ is at least ${\text {diam}}(C)=(|C|-1)/2\ge 3$. Thus there exists a $w\in C$ such that $N(v)\cap N(w)=\varnothing$.

A chain graph is a bipartite graph $(L \cup R, E)$ where L and R are linearly ordered by inclusion of neighbourhoods. Its biadjacency matrix has the form indicated in Fig. 11, see [5] for details. In the monotone representation, it is an easy observation that the graph has a decomposition into chain graphs, as indicated in Fig. 12, where L is partitioned in $D_1,D_3,\ldots$ and R into $D_2,D_4,\ldots$. Brandstädt and Lozin showed in [3] that such a partition exists. For vertices v and w as above, N(w) and its neighbours induce a monotone subgraph $N_w$ of G, as indicated in Fig. 12. The vertex set of $N_w$ is $\{x\in L\cup R:{\text {dist}}(w,x)\le 2\}$. Clearly $N_w$ is the union of two chain graphs $C_w,C'_w$, with $C_w$ lying in the rows below and including w, and $C'_w$ in the rows above. Using the algorithm of [14], the monotone representation of $G_v$ determines this split. Then we can construct a representation of the adjacency matrix A(G) of G as indicated in the first diagram in Fig. 13, where $D_2=N(w)$, $\mathcal {C}_1=\mathcal {C}_w$ (transposed), and $\mathcal {C}_7=\mathcal {C}'_w$. The chain graphs $\mathcal {C}_2,\ldots ,\mathcal {C}_6$ are a decomposition of the monotone graph $G_w$. Note that the ordering of the chain graphs in the decomposition is circular, and the second diagram in Fig. 13 gives an equivalent representation to the first, where $\mathcal {C}_1$ (transposed) is moved from the first to the last position.

Fig. 11.

Chain graph structure

Fig. 12.

Decomposition of a monotone graph/neighbourhood of w in $G_v$

Fig. 13.

Decomposition of A(G) for a quasimonotone graph G

Lemma 16

A flawless graph G which has an odd hole of size at least 7 is quasimonotone if and only if it has such a decomposition and does not contain a prehole. If there are k chain graphs in the decomposition, then k is odd, and the shortest hole in G has k vertices.

5.2 Recognising Preholes

Let $G=(V,E)$ be a flawless graph with a hole of size $\ell \ge 7$. Lemma 16 can determine whether or not G is quasimonotone provided it does not contain a prehole. We now consider recognition of a prehole in such a graph.

We use the partition of V from Sect. 5.1 into independent sets $D_1,D_2,\ldots ,D_\ell$, where $D_{\ell +1}\equiv D_1$. All edges in E run between $D_i$ and $D_{i+1}$ ($i\in [\ell ]$). Let $G_i=G[D_i\cup D_{i+1}]$, with edge set $E_i$, and let $\overline{G}_i=(V,E\setminus E_i)$. Note that $G_i$ is a chain graph and $\overline{G}_i$ is a monotone graph. Thus $\overline{G}_i$ is bipartition, with bipartition $L{:}R$, say, with $D_i,D_{i+1}\in L$.

Fig. 14.

Possible crossover

We search for possible crossovers in $G_i$. These are pairs $a,b\in D_{i+1}$, $c,d\in D_i$, such that $ac,ad,bc,bd\in E$. We list all such quadruples a, b, c, d, $O(n^4)$ in total, see Fig. 14. Given any quadruple, we attempt to determine vertex disjoint paths $P_{ac},P_{bd}$ in $\overline{G}_i$ between a, c and b, d or between a, d and b, c. See Fig. 15, cases (a) and (b). We can do this in $O(n|E|)=O(n^3)$ time by network flow. Both paths are even length, since $G_i$ is bipartite and $a,b,c,d\in L$.

Fig. 15.

Vertex-disjoint paths, case (a) left, (b) right

If these paths do not exist, we discard this quadruple and consider the next in the list. If these paths do exist, in case (a) we have found a crossover prehole $P_{ac},ad,P_{bd},bc$, in case (b) we have found a Möbius prehole $P_{ad},bd,P_{bc},ac$. This is clearly a cycle with even length. That it is a prehole is certified by reversing the bipartition on $P_{ac}$ in case (a), $P_{ad}$ in case (b), as shown in Fig. 16. Thus we can detect a prehole, or show that none exists, in $O(n^7)$ time. If a prehole exists the input graph is not quasimonotone.

Fig. 16.

Preholes, left with crossover (a), right of Möbius type (b).

6 Flawless Graphs Without Long Holes

6.1 Minimal Preholes in Hole-Free Graphs

Let C be any minimal prehole in a flawless hole-free graph G. A triangle in G[C] will be called an interior triangle of C if it has no edge in common with C, a crossing triangle if it has one edge in common with C, and a cap of C if it has two edges in common with C.

Lemma 17

If C is a minimal prehole in a flawless graph with $|C|>12$, then G[C] has no interior or crossing triangles, and C is determined by two edge-disjoint caps.

Let $T_1$, $T_2$ be caps of C, such that $v_i\in T_i$ is adjacent to two edges of C $(i=1,2)$. Then there are two edge-disjoint $(v_1,\ldots , v_2)$ paths $P_1,P_2$ in C (Fig. 17).

Fig. 17.

A prehole and its Hamilton subgraph

Lemma 18

Let C, with $|C|>12$, be a minimal prehole in a flawless hole-free graph determined by $v_1,v_2$, and let $C'=C\setminus \{v_1,v_2\}$. Then $G[C']$ is a Hamilton monotone graph, and all chords of $C'$ connect $P_1$ to $P_2$.

Proof

Clearly $G[C']$ is Hamilton, since G[C] is Hamilton. Now $C'$ cannot be a prehole, since it is strictly smaller than C. So $G[C']$ cannot contain a triangle, by Lemma 17. It cannot contain a larger odd cycle, since then it would contain a triangle, by the argument of Lemma 17. Therefore, $G[C']$ is bipartite and, since $G\in \textsc {HoleFree}$, contains no hole. So, since $G\in \textsc {Flawless}$, $G[C']$ is a monotone graph. Suppose uv is an edge of $G[C']$ with $u,v\in P_1$. Then, since G[C] has only even chords, the even chord uv and the segment of $P_1$ between u and v forms an odd cycle, giving a contradiction.    $\square$

Thus any minimal prehole C comprises a Hamilton monotone graph $G[C']$, to which we add two caps $T_1$, $T_2$. We may also add edges from $v_1$ and $v_2$ to $C'$, as long as they are even chords in C.

Lemma 19

Let C be a minimal prehole with a cap at $v\in \{v_1,v_2\}$. Then there are at most two chords from v, and both must be connected to either $P_1$ or $P_2$.

Let $T_1=\{v_1,u_1,w_1\}$, $T_2=\{v_2,u_2,w_2\}$ be any two edge-disjoint triangles in a flawless graph G. Let M be the component of $G\setminus \{v_1,v_2\}$ containing $u_1w_1$, $u_2w_2$, if such a component exists. If M does not exist then $v_1,v_2$ clearly do not determine a prehole.

Lemma 20

$C=(v_1,u_1,\ldots ,u_2,v_2,w_2,\ldots ,w_1,v_1)$ determines a minimal prehole if and only if M is a monotone graph containing two vertex-disjoint paths between $u_1,u_2$ and $v_1,v_2$.

6.2 Preholes Containing 5-Holes and Triangles

It remains to consider preholes in graphs which contain 5-holes. Preholes determined by two triangles will be dealt with as in Sect. 6.1.

Lemma 21

Let C be a minimal prehole in a flawless graph G which contains no odd hole of size greater than five. If C connects a 5-hole and a triangle, or if C connects two 5-holes, then $|C|\le 12$.

7 Conclusion and Discussion

In [6] we considered the problem of ergodicity and rapid mixing of the switch chain in hereditary graph classes. We gave a complete answer to the ergodicity question, and showed rapid mixing for the new class of quasimonotone graphs. This led us to introduce a new “quasi-” operator on bipartite graph classes, which is of independent interest. Quasimonotone graphs are a particular case of this construction. Another interesting class is the class of odd-chordal graphs, which are the quasi-chordal bipartite graphs. This is close to the largest class for which the switch chain is ergodic.

A more straightforward approach to recognising quasimonotone graphs would be provided by a polynomial time recognition algorithm for odd-chordal graphs. This is equivalent to the detection of preholes in a graph. We have considered this question, but we leave it as an open problem. The only evidence we can provide is that it is $\mathbb {NP}$-complete to determine if a graph is a prehole, which may be a harder question. Nonetheless, the $\mathbb {NP}$-completeness proof suggests that an efficient algorithm for recognising odd-chordal graphs may be elusive.