51³Ô¹Ï

Topic

Chordality of Digraphs, Signed Graphs, and Signed Bigraphs

Department of Mathematics and Statistics

Date & location

• Tuesday, July 8, 2025
• 10:00 A.M.
• David Turpin Building, Room A203

Examining Committee

Supervisory Committee

• Dr. Jing Huang, Department of Mathematics and Statistics, 51³Ô¹Ï (Supervisor)
• Dr. Jonathan Noel, Department of Mathematics and Statistics, UVic (Member)
• Dr. Venkatesh Srinivasan, Department of Computer Science, UVic (Outside Member)

External Examiner

• Prof. Shamik Ghosh, Department of Mathematics, Jadavpur University

Chair of Oral Examination

• Dr. David Scoones, Department of Economics, UVic

Abstract

Chordal graphs and chordal bigraphs enjoy beautiful characterizations, in terms of forbidden subgraphs, vertex or edge orderings, and tree-like representations. A digraph analogue of chordal graphs was introduced by Haskins and Rose. Unfortunately, a forbidden subdigraph characterization of chordal digraphs is not known and finding such a characterization seems to be a difficult problem. The study of chordal digraphs has been restricted to various classes of digraphs, such as semicomplete digraphs, quasi-transitive digraphs, extended semicomplete digraphs and locally semicomplete digraphs.

In this dissertation, we introduce the new class of weakly quasi-transitive digraphs as a common generalization of semicomplete digraphs, quasi-transitive digraphs and symmetric digraphs. We show that weakly quasi-transitive digraphs can be obtained from these three classes of digraphs by substitutions. As a consequence, weakly quasitransitive digraphs admit a recursive construction. This construction theorem allows us to find a forbidden subdigraph characterization of weakly quasi-transitive chordal digraphs. In addition, we use it to prove that the small quasi-kernel conjecture holds for weakly quasi-transitive digraphs.

We extend the notion of chordality to signed graphs and signed bigraphs Interestingly, chordal signed graphs are equivalent to strict chordal digraphs studied by Hell and Hernandez-Cruz. Their forbidden subdigraph characterization of strict chordal digraphs can be translated to a forbidden subgraph characterization of chordal signed graphs. We give a forbidden subgraph characterization of chordal signed bigraphs. The forbidden subgraphs for chordal signed bigraphs are analogous to those for chordal signed graphs but the proofs are much more complicated and intriguing.