No description available.

Thesis--Auburn University, 2009. / Abstract. Vita. Includes bibliographical references (p. 21).

M.Sc. / Within the field of Graph Theory the many ways in which graphs can be coloured have received a lot of attention over the years. T.R. Jensen and B. Toft provided a summary in [8] of the most important results and research done in this field. These results were cited by R. Diestel in [5] as “The Four Colour Problem” wherein it is attempted to colour every map with four colours in such a way that adjacent countries will be assigned different colours. This was first noted as a problem by Francis Guthrie in 1852 and later, in 1878, by Cayley who presented it to the London Mathematical Society. In 1879 Kempe published a proof, but it was incorrect and lead to the adjustment by Heawood in 1890 to prove the five colour theorem. In 1977 Appel and Haken were the first to publish a solution for the four colour problem in [2] of which the proof was mostly based on work done by Birkhoff and Heesch. The proof is done in two steps that can be described as follows: firstly it is shown that every triangulation contains at least one of 1482 certain “unavoidable configurations” and secondly, by using a computer, it is shown that each of these configurations is “reducible”. In this context the term “reducible” is used in the sense that any plane triangulation containing such a configuration is 4-colourable by piecing together 4- colourings of smaller plane triangulations. These two steps resulted in an inductive proof that all plane triangulations and therefore all planar graphs are 4-colourable.

No description available.

Thesis (M.A.)--The University of North Carolina at Greensboro, 2008. / Directed by Paul Duvall; submitted to the Dept. of Mathematical Sciences. Title from PDF t.p. (viewed Aug. 26, 2009). Includes bibliographical references (p. 38).

Orientador: Christiane Neme Campos / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T00:02:03Z (GMT). No. of bitstreams: 1 Galvao_KaioKaram_M.pdf: 1971760 bytes, checksum: e2f60ab09595b03fa6da5051cd78e3f3 (MD5) Previous issue date: 2013 / Resumo: Em 1971, Fulkerson propôs a seguinte conjetura: todo grafo cúbico sem arestas de corte admite seis emparelhamentos perfeitos tais que cada aresta do grafo pertence a exatamente dois destes emparelhamentos. A Conjetura de Fulkerson tem desafiado pesquisadores desde sua publicação. Esta conjetura é facilmente verificada para grafos cúbicos 3-aresta-coloráveis. Portanto, a dificuldade do problema reside em estabelecer a conjetura para grafos cúbicos sem arestas de corte que não possuem 3-coloração de arestas. Estes grafos são chamados snarks. Nesta dissertação, a Conjetura de Fulkerson e os snarks são introduzidos com ¿ênfase em sua história e resultados mais relevantes. Alguns resultados relacionados à Conjetura de Fulkerson são apresentados, enfatizando suas conexões com outras conjeturas. Um breve histórico do Problema das Quatro Cores e suas relações com snarks também são apresentados. Na segunda parte deste trabalho, a Conjetura de Fulkerson é verificada para algumas famílias infinitas de snarks construídas com o método de Loupekine, utilizando subgrafos do Grafo de Petersen. Primeiramente, mostramos que a família dos LP0-snarks satisfaz a Conjetura de Fulkerson. Em seguida, generalizamos este resultado para a família mais abrangente dos LP1-snarks. Além disto, estendemos estes resultados para Snarks de Loupekine construídos com subgrafos de snarks diferentes do Grafo de Petersen / Abstract: In 1971, Fulkerson proposed a conjecture that states that every bridgeless cubic graph has six perfect matchings such that each edge of the graph belongs to precisely two of these matchings. Fulkerson's Conjecture has been challenging researchers since its publication. It is easily verified for 3-edge-colourable cubic graphs. Therefore, the difficult task is to settle the conjecture for non-3-edge-colourable bridgeless cubic graphs, called snarks. In this dissertation, Fulkerson's Conjecture and snarks are presented with emphasis in their history and remarkable results. We selected some results related to Fulkerson's Conjecture, emphasizing their reach and connections with other conjectures. It is also presented a brief history of the Four-Colour Problem and its connections with snarks. In the second part of this work, we verify Fulkerson's Conjecture for some infinite families of snarks constructed with Loupekine's method using subgraphs of the Petersen Graph. More specifically, we first show that the family of LP0-snarks satisfies Fulkerson's Conjecture. Then, we generalise this result by proving that Fulkerson's Conjecture holds for the broader family of LP1-snarks. We also extend these results to even more general Loupekine Snarks constructed with subgraphs of snarks other than the Petersen Graph / Mestrado / Ciência da Computação / Mestre em Ciência da Computação