This PhD thesis is comprised of 3 results in computational geometry
and graph theory.
In the first paper, I demonstrate that the piercing number of a set S of pairwise intersecting convex shapes in the plane is bounded by O(\alpha(S)), where \alpha(S) is the fatness of the set S, improving upon the previous upper-bound of O(\alpha(S)^2).
In the second article, I show that anagram-free vertex colouring of a 2\times n square grid requires a number of colours that increases with n. This answers an open question in Wilson's thesis and shows that even graphs of pathwidth 2 do not have anagram-free colouring with a bounded number of colours.
The third article is a study on the geodesic anagram-free chromatic number of chordal and interval graphs. \emph{Geodesic anagram-free chromatic number} is defined as the minimum number of colours required to colour a graph such that all shortest paths between any pair of vertices are coloured anagram-free. In particular, I prove that the geodesic anagram-free chromatic number of a chordal graph G is 32p'w, where p' is the pathwidth of the subtree intersection representation graph (tree) of G, and w is the clique number of G. Additionally, I prove that the geodesic anagram-free chromatic number of an interval graph is bounded by 32p, where p is the pathwidth of the interval graph. This PhD thesis is comprised of 3 results in computational geometry and graph theory.
| Identifer | oai:union.ndltd.org:uottawa.ca/oai:ruor.uottawa.ca:10393/45610 |
| Date | 07 November 2023 |
| Creators | Bazargani, Saman |
| Contributors | Dujmović, Vida, Bose, Prosenjit, Morin, Pat |
| Publisher | Université d'Ottawa / University of Ottawa |
| Source Sets | Université d’Ottawa |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
Page generated in 0.002 seconds