The orientation completion problem for a hereditary class C of oriented graphs asks whether a given partially oriented graph can be completed to a graph belonging to C. This problem was introduced recently and is a generalization of several existing problems, including the recognition problem for certain classes of graphs and the representation extension problem for proper interval graphs. A local tournament is an oriented graph in which the in-neighbourhood as well as the out-neighbourhood of each vertex induces a tournament. Local tournaments are a well-studied class of oriented graphs that generalize tournaments and their underlying graphs are intimately related to proper circular-arc graphs. Proper interval graphs are precisely those which can be oriented as acyclic local tournaments. The orientation completion problems for the class of local tournaments and the class of acyclic local tournaments have been shown to be polynomial-time solvable. In this thesis, we characterize the partially oriented graphs that can be completed to local tournaments by finding a complete list of obstructions. These are in a sense the minimal partially oriented graphs that cannot be completed to local tournaments. We also determine the minimal partially oriented graphs that cannot be completed to acyclic local tournaments. / Graduate
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/12024 |
| Date | 23 August 2020 |
| Creators | Hsu, Kevin |
| Contributors | Huang, Jing |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
| Rights | Available to the World Wide Web |
Page generated in 0.0019 seconds