Two problems in graph theory

Kučera, Stanislav (2019) Two problems in graph theory. MPhil thesis, London School of Economics and Political Science.

Text - Submitted Version Download (451kB)

Abstract

In the thesis we study two topics in graph theory. The first one is concerned with the famous conjecture of Hadwiger that every graph G without a minor of a complete graph on t +1 vertices can be coloured with t colours. We investigate how large an induced subgraph of G can be, so that the subgraph can be coloured with t colours. We show that G admits a t-colourable induced subgraph on more than half of its vertices. Moreover, if such graph G on n vertices does not contain any triangle, we show it admits a t-colourable induced subgraph on at least 4n=5 vertices and show even better bounds for graphs with larger odd girth. The second topic is a variant of a well-known two player Maker-Breaker connectivity game in which players take turns choosing an edge in each step in order to achieve their respective goals. While a complete characterisation is known for the connectivity game in which both players choose a single edge, much less is known in all other cases. We study the variant in which both players choose two edges, or more generally, the variant in which the first player decides whether both players choose one or two edges in the next round.

Item Type:	Thesis (MPhil)
Additional Information:	© 2019 Stanislav Kučera
Library of Congress subject classification:	Q Science > QA Mathematics
Sets:	Departments > Mathematics
Supervisor:	van den Heuvel, Jan
URI:	http://etheses.lse.ac.uk/id/eprint/4188

Actions (login required)

Record administration - authorised staff only