The odd edge-connectivity between two vertices in a graph is the maximum number λ_{o}(u, v) of edge-disjoint (u, v)-trails of odd length. In this thesis, we define the perimeter of a vertex-set, a natural upper bound for the odd edge-connectivity between some of its constituent pairs. Our central result is an approximate characterization of odd edge-connectivity: λ_{o}(u, v) is bounded above and below by constant factors of the usual edge-connectivity λ(u, v) and/or the minimum perimeter among vertex-sets containing u and v.

The relationship between odd edge-connectivity and perimeter has many implications, most notably a loose packing–covering duality for odd trails. (In contrast, odd paths do not obey any such duality.) For Eulerian graphs, we obtain a second, independent proof of the packing–covering duality with a significantly better constant factor. Both proofs can be implemented as polynomial-time approximation algorithms for λ_{o}(u, v). After observing that perimeter satisfies a submodular inequality, we are able to prove an analogue of the Gomory–Hu Theorem for sets of minimum perimeter and, consequently, to construct an efficient data structure for storing approximate odd edge-connectivities for all vertex pairs in a graph.

The last part of the thesis studies more complicated systems of odd trails. A totally odd immersion of a graph H in another graph G is a representation in which vertices in H correspond to vertices in G and edges in H correspond to edge-disjoint odd trails in G. Using our perimeter version of the Gomory–Hu Theorem, we describe the rough structure of graphs with no totally odd immersion of the complete graph K_{t}. Finally, we suggest a totally odd immersion variant of Hadwiger’s Conjecture and show that it is true for almost all graphs.

Odd disjoint trails and totally odd graph immersions. Ross Churchley. PhD thesis, Simon Fraser University. January 2016. (Senior supervisor: Bojan Mohar)

Despite Menger’s famous duality between packings and coverings of (u, v)-paths in a graph, there is no duality when we require the paths be odd: a graph with no two edge-disjoint odd (u, v)-paths may need an arbitrarily large number of edges to cover all such paths. In this paper, we study the relaxed problem of packing odd trails. Our main result is an approximate duality for odd trails: if ν(u, v) denotes the maximum number of edge-disjoint (u, v)-trails of odd length in a graph G and τ(u, v) denotes the minimum number of edges that intersect every such trail, then ν(u, v) ≤ τ(u, v) ≤ ν(u, v). The proof leads to a polynomial-time algorithm to find, for any given k, either k edge-disjoint odd (u, v)-trails or a set of fewer than 8k edges intersecting all odd (u, v)-trails. This yields a constant factor approximation algorithm for the packing number ν(u, v).

This result generalizes to the setting of signed graphs and to the setting of group-labelled graphs, in which case “odd length” is replaced by “non-unit product of labels”. The motivation for this result comes from the study of totally odd graph immersions, and our results explain, in particular, why there is an essential difference between the totally odd weak and strong immersions.

Weak duality for packing edge-disjoint odd (u, v)-trails. Ross Churchley, Bojan Mohar, and Hehui Wu. *Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016),* 2086–2094. January 2016.

Polarity and monopolarity are properties of graphs defined in terms of the existence of certain vertex partitions; graphs with polarity and monopolarity are respectively called polar and monopolar graphs. These two properties commonly generalize bipartite and split graphs, but are hard to recognize in general. In this article we identify two classes of graphs, triangle-free graphs and claw-free graphs, restricting to which provide novel impact on the complexity of the recognition problems. More precisely, we prove that recognizing polarity or monopolarity remains NP-complete for triangle-free graphs. We also show that for claw-free graphs the former is NP-complete and the latter is polynomial time solvable. This is in sharp contrast to a recent result that both polarity and monopolarity can be recognized in linear time for line graphs. Our proofs for the NP-completeness are simple reductions. The polynomial time algorithm for recognizing the monopolarity of claw-free graphs uses a subroutine similar to the well-known breadth-first search algorithm and is based on a new structural characterization of monopolar claw-free graphs, a generalization of one for monopolar line graphs obtained earlier.

On the polarity and monopolarity of graphs. Ross Churchley and Jing Huang. *Journal of Graph Theory* 76 (2), 138–148. June 2014.

Polar, monopolar, and unipolar graphs are defined in terms of the existence of certain vertex partitions. Although it is polynomial to determine whether a graph is unipolar and to find whenever possible a unipolar partition, the problems of recognizing polar and monopolar graphs are both NP-complete in general. These problems have recently been studied for chordal, claw-free, and permutation graphs. Polynomial time algorithms have been found for solving the problems for these classes of graphs, with one exception: polarity recognition remains NP-complete in claw-free graphs. In this paper, we connect these problems to edge-coloured homomorphism problems. We show that finding unipolar partitions in general and finding monopolar partitions for certain classes of graphs can be efficiently reduced to a polynomial-time solvable 2-edge-coloured homomorphism problem, which we call the colour-bipartition problem. This approach unifies the currently known results on monopolarity and extends them to new classes of graphs.

Solving partition problems with colour-bipartitions. Ross Churchley and Jing Huang. *Graphs and Combinatorics* 30 (2), 353–364. March 2014.

Given graphs G, H, is it possible to find a matching which, when deleted from G, destroys all copies of H? The answer is obvious for some inputs—notably, when G is a large complete graph the answer is “no”—but in general this can be a very difficult question. In this thesis, we study this decision problem when H is a fixed tree or cycle; our aim is to identify those H for which it can be solved efficiently.

The H-transverse matching problem, TM(H) for short, asks whether an input graph admits a matching M such that no subgraph of G − M is isomorphic to H. The main goal of this thesis is the following dichotomy. When H is a triangle or one of a few small-diameter trees, there is a polynomial-time algorithm to find an H-transverse matching if one exists. However, TM(H) is NP-complete when H is any longer cycle or a tree of diameter ≥ 4. In addition, we study the restriction of these problems to structured graph classes.

On graph-transverse matchings. Ross Churchley. MSc thesis, University of Victoria. August 2012. (Senior supervisor: Jing Huang)

The stable transversal problem for a fixed graph H asks whether a graph contains a stable set that meets every induced copy of H in the graph. Stable transversal problems generalize several vertex partition problems and have been studied for various classes of graphs. Following a result of Farrugia, the stable transversal problem for each C_{l} with l ≥ 3 is NP-complete. In this paper, we study an edge version of these problems. Specifically, we investigate the problem of determining whether a graph contains a matching that meets every copy of H. We show that the problem for C_{3} is polynomial and for each C_{l} with l ≥ 4 is NP-complete. Our results imply that the stable transversal problem for each C_{l} with l ≥ 4 remains NP-complete when it is restricted to line graphs. We show by contrast that the stable transversal problem for C_{3}, when restricted to line graphs, is polynomial.

Complexity of cycle-transverse matching problems. Ross Churchley, Jing Huang, and Xuding Zhu. *Lecture Notes in Computer Science* 7056, 135–143. 2011.

The list monopolar partition problem asks whether a graph G together with lists L(v) ⊆ {0, 1}, v ∈ V(G) admits a mapping f: V(G) → {0, 1} such that f(v) ∈ L(v) for each source induces an independent set and f^{−1}(1) induces a disjoint union of cliques in G. This problem is NP-complete in general. We show that the problem is solvable in time O(n^{2}m) for claw-free graphs where n and m are the numbers of vertices and edges respectively in the input graph.

List-monopolar partitions of claw-free graphs. Ross Churchley and Jing Huang. *Discrete Mathematics* 312 (17), 2545–2549. September 2012.

A graph is polar if its vertex set can be partitioned into A and B in such a way that A induces a complete multipartite graph and B induces a disjoint union of cliques (i.e., the complement of a complete multipartite graph). Polar graphs naturally generalize several classes of graphs such as bipartite, cobipartite, and split graphs. The problem of recognizing polar graphs is NP-complete in general. However, it has been shown to be polynomial for several classes of graphs, including cographs and chordal graphs. In this paper, we study the problem of recognizing graphs whose line graphs are polar. It turns out that the core part of this problem lies in determining whether the edge set of a graph admits a partition (A, B) so that A induces a P_{3}-free subgraph (i.e., a matching) and B induces a P_{4}-free subgraph. We give a structural characterization of such graphs. The characterization enables us to devise an O(n) time algorithm to solve the stated recognition problem.

Line-polar graphs: characterization and recognition. Ross Churchley and Jing Huang. *SIAM Journal on Discrete Mathematics* 25 (3), 1269–1284. August 2011.