Graph colourings and games
<p>Graph colourings and combinatorial games are two very widely studied topics in discrete mathematics. This thesis addresses the computational complexity of a range of problems falling within one or both of these subjects.</p><p>Much of the thesis is concerned with the computation...
| מחבר ראשי: | |
|---|---|
| מחברים אחרים: | |
| פורמט: | Thesis |
| שפה: | English |
| יצא לאור: |
2012
|
| נושאים: |
| _version_ | 1826289740286001152 |
|---|---|
| author | Meeks, KFT |
| author2 | Scott, A |
| author_facet | Scott, A Meeks, KFT |
| author_sort | Meeks, KFT |
| collection | OXFORD |
| description | <p>Graph colourings and combinatorial games are two very widely studied topics in discrete mathematics. This thesis addresses the computational complexity of a range of problems falling within one or both of these subjects.</p><p>Much of the thesis is concerned with the computational complexity of problems related to the combinatorial game (Free-)Flood-It, in which players aim to make a coloured graph monochromatic ("flood" the graph) with the minimum possible number of flooding operations; such problems are known to be computationally hard in many cases. We begin by proving some general structural results about the behaviour of the game, including a powerful characterisation of the number of moves required to flood a graph in terms of the number of moves required to flood its spanning trees; these structural results are then applied to prove tractability results about a number of flood-filling problems. We also consider the computational complexity of flood-filling problems when the game is played on a rectangular grid of fixed height (focussing in particular on 3xn and 2xn grids), answering an open question of Clifford, Jalsenius, Montanaro and Sach.</p><p>The final chapter concerns the parameterised complexity of list problems on graphs of bounded treewidth. We prove structural results determining the list edge chromatic number and list total chromatic number of graphs with bounded treewidth and large maximum degree, which are special cases of the List (Edge) Colouring Conjecture and Total Colouring Conjecture respectively. Using these results, we show that the problem of determining either of these quantities is fixed parameter tractable, parameterised by the treewidth of the input graph. Finally, we analyse a list version of the Hamilton Path problem, and prove it to be W[1]-hard when parameterised by the pathwidth of the input graph. These results answer two open questions of Fellows, Fomin, Lokshtanov, Rosamond, Saurabh, Szeider and Thomassen.</p> |
| first_indexed | 2024-03-07T02:33:30Z |
| format | Thesis |
| id | oxford-uuid:a805a379-f891-4250-9a7d-df109f9f52e2 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T02:33:30Z |
| publishDate | 2012 |
| record_format | dspace |
| spelling | oxford-uuid:a805a379-f891-4250-9a7d-df109f9f52e22022-03-27T02:58:33ZGraph colourings and gamesThesishttp://purl.org/coar/resource_type/c_db06uuid:a805a379-f891-4250-9a7d-df109f9f52e2CombinatoricsComputer science (mathematics)Applications and algorithmsEnglishOxford University Research Archive - Valet2012Meeks, KFTScott, A<p>Graph colourings and combinatorial games are two very widely studied topics in discrete mathematics. This thesis addresses the computational complexity of a range of problems falling within one or both of these subjects.</p><p>Much of the thesis is concerned with the computational complexity of problems related to the combinatorial game (Free-)Flood-It, in which players aim to make a coloured graph monochromatic ("flood" the graph) with the minimum possible number of flooding operations; such problems are known to be computationally hard in many cases. We begin by proving some general structural results about the behaviour of the game, including a powerful characterisation of the number of moves required to flood a graph in terms of the number of moves required to flood its spanning trees; these structural results are then applied to prove tractability results about a number of flood-filling problems. We also consider the computational complexity of flood-filling problems when the game is played on a rectangular grid of fixed height (focussing in particular on 3xn and 2xn grids), answering an open question of Clifford, Jalsenius, Montanaro and Sach.</p><p>The final chapter concerns the parameterised complexity of list problems on graphs of bounded treewidth. We prove structural results determining the list edge chromatic number and list total chromatic number of graphs with bounded treewidth and large maximum degree, which are special cases of the List (Edge) Colouring Conjecture and Total Colouring Conjecture respectively. Using these results, we show that the problem of determining either of these quantities is fixed parameter tractable, parameterised by the treewidth of the input graph. Finally, we analyse a list version of the Hamilton Path problem, and prove it to be W[1]-hard when parameterised by the pathwidth of the input graph. These results answer two open questions of Fellows, Fomin, Lokshtanov, Rosamond, Saurabh, Szeider and Thomassen.</p> |
| spellingShingle | Combinatorics Computer science (mathematics) Applications and algorithms Meeks, KFT Graph colourings and games |
| title | Graph colourings and games |
| title_full | Graph colourings and games |
| title_fullStr | Graph colourings and games |
| title_full_unstemmed | Graph colourings and games |
| title_short | Graph colourings and games |
| title_sort | graph colourings and games |
| topic | Combinatorics Computer science (mathematics) Applications and algorithms |
| work_keys_str_mv | AT meekskft graphcolouringsandgames |