Spelling suggestions: "subject:"kelly's heorem"" "subject:"kelly's atheorem""
1 |
Helly-Type TheoremsDavenport, Edward W. 08 1900 (has links)
The purpose of this paper is to present two proofs of Helly's Theorem and to use it in the proofs of several theorems classified in a group called Helly-type theorems.
|
2 |
Transversals of Geometric Objects and Anagram-Free ColouringBazargani, Saman 07 November 2023 (has links)
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.
|
Page generated in 0.0543 seconds