Matchings, factors and cycles in graphs
A matching in a graph is a set of pairwise nonadjacent edges, a k-factor is a k-regular spanning subgraph, and a cycle is a closed path. This thesis has two parts. In Part I (by far the larger part) we study sufficient conditions for structures involving matchings, factors and cycles. The three mai...
| Main Author: | |
|---|---|
| Format: | Thesis (University of Nottingham only) |
| Language: | English |
| Published: |
2008
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/10530/ |
| _version_ | 1848791094110715904 |
|---|---|
| author | Philpotts, Adam Richard |
| author_facet | Philpotts, Adam Richard |
| author_sort | Philpotts, Adam Richard |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | A matching in a graph is a set of pairwise nonadjacent edges, a k-factor is a k-regular spanning subgraph, and a cycle is a closed path.
This thesis has two parts. In Part I (by far the larger part) we study sufficient conditions for structures involving matchings, factors and cycles. The three main types of conditions involve: the minimum degree; the degree sum of pairs of nonadjacent vertices (Ore-type conditions); and the neighbourhoods of independent sets of vertices. We show that most of our theorems are best possible by giving appropriate extremal graphs.
We study Ore-type conditions for a graph to have a Hamilton cycle or 2-factor containing a given matching or path-system, and for any matching and single vertex to be contained in a cycle. We give Ore-type and neighbourhood conditions for a matching L of l edges to be contained in a matching of k edges (l < k). We generalise two different aspects of this result: the l = 0 case with an Ore-type condition for a heavy matching in an edge-weighted graph; and the conditions for a perfect matching containing L with degree and neighbourhood conditions for a k-factor (k > 2) containing a given set of edges. We also establish neighbourhood conditions for the existence of a cycle of length at least k.
A list-edge-colouring of a graph is an assignment of a colour to each edge from its own list of colours. In Part II we study edge colourings of powers of cycles, and prove the List-Edge-Colouring Conjecture for squares of cycles of odd length. |
| first_indexed | 2025-11-14T18:23:02Z |
| format | Thesis (University of Nottingham only) |
| id | nottingham-10530 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T18:23:02Z |
| publishDate | 2008 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-105302025-02-28T11:08:40Z https://eprints.nottingham.ac.uk/10530/ Matchings, factors and cycles in graphs Philpotts, Adam Richard A matching in a graph is a set of pairwise nonadjacent edges, a k-factor is a k-regular spanning subgraph, and a cycle is a closed path. This thesis has two parts. In Part I (by far the larger part) we study sufficient conditions for structures involving matchings, factors and cycles. The three main types of conditions involve: the minimum degree; the degree sum of pairs of nonadjacent vertices (Ore-type conditions); and the neighbourhoods of independent sets of vertices. We show that most of our theorems are best possible by giving appropriate extremal graphs. We study Ore-type conditions for a graph to have a Hamilton cycle or 2-factor containing a given matching or path-system, and for any matching and single vertex to be contained in a cycle. We give Ore-type and neighbourhood conditions for a matching L of l edges to be contained in a matching of k edges (l < k). We generalise two different aspects of this result: the l = 0 case with an Ore-type condition for a heavy matching in an edge-weighted graph; and the conditions for a perfect matching containing L with degree and neighbourhood conditions for a k-factor (k > 2) containing a given set of edges. We also establish neighbourhood conditions for the existence of a cycle of length at least k. A list-edge-colouring of a graph is an assignment of a colour to each edge from its own list of colours. In Part II we study edge colourings of powers of cycles, and prove the List-Edge-Colouring Conjecture for squares of cycles of odd length. 2008 Thesis (University of Nottingham only) NonPeerReviewed application/pdf en arr https://eprints.nottingham.ac.uk/10530/1/finalthesis.pdf Philpotts, Adam Richard (2008) Matchings, factors and cycles in graphs. PhD thesis, University of Nottingham. Hamilton cycle Ore-type condition neighbourhood condition neighborhood condition Alon-Tarsi method edge colouring edge coloring |
| spellingShingle | Hamilton cycle Ore-type condition neighbourhood condition neighborhood condition Alon-Tarsi method edge colouring edge coloring Philpotts, Adam Richard Matchings, factors and cycles in graphs |
| title | Matchings, factors and cycles in graphs |
| title_full | Matchings, factors and cycles in graphs |
| title_fullStr | Matchings, factors and cycles in graphs |
| title_full_unstemmed | Matchings, factors and cycles in graphs |
| title_short | Matchings, factors and cycles in graphs |
| title_sort | matchings, factors and cycles in graphs |
| topic | Hamilton cycle Ore-type condition neighbourhood condition neighborhood condition Alon-Tarsi method edge colouring edge coloring |
| url | https://eprints.nottingham.ac.uk/10530/ |