On colourings of graphs.
Published: 2005
Language: eng
Number of pages: 145
Description: Finally, we prove a conjecture posed independently by Wang and Lih [WL01] and Fijavz, Juvan, Mohar, and Skrekovski [FJMS02] that states that planar graphs without 7-cycles are 4-choosable. This, in addition to previously known results, implies that a planar graph without k-cycles is 4-choosable for any k &isin; {3, 4, 5, 6, 7}.Then we focus our study on planar graphs using the Discharging Method. We first prove an open case of Vizing's List Chromatic Index Conjecture [Viz76] from [ZW04] by showing that every planar graph without 4-cycles and with maximum degree 5 is 6-edge-choosable. Then we prove the conjecture for planar graphs without 6-cycles, i.e. we prove that every planar graph G without 6-cycles is (Delta(G) + 1)-edge choosable.In this thesis we study various colouring problems on graphs.A graph G is k-critical if it has chromatic number k, but every proper subgraph of G is (k - 1)-colourable. Gallai [Gal63] conjectured that a 4-critical graph on n vertices has at least   53n-2 3  edges. The lowgraph of G is the subgraph induced by vertices of degree k - 1. We prove Gallai's conjecture for every 4-critical graph whose lowgraph is connected.
Notes: Source: Dissertation Abstracts International, Volume: 66-10, Section: B, page: 5494.

Advisor: M. Molloy.

Thesis (Ph.D.)--University of Toronto, 2005.

Electronic version licensed for access by U. of T. users.