1. RSUIR at Rangsit University
2. RSU Digital Collection
3. วิทยาลัยนวัตกรรมดิจิทัลเทคโนโลยี College of Digital Innovation Technology
4. ICT-Research

Title:	Research project report Hadwiger's Conjecture and a special case of Hadwiger's Conjecture
Authors:	Wongsakorn Charoenpanitser
Keywords:	Graph theory -- Research;Hadwiger’s conjecture;Computer science;Four color theorem
Issue Date:	2020
Publisher:	Research Institute of Rangsit University
metadata.dc.description.other-abstract:	What is the minimum number of colors required to color a map such that no two adjacent regions having the same color? Three colors are not enough to because a map with four reqions with each region contacting the three other regions. However, no map have ever been found that four colors are not enough. This question first posed in the early 1850s and not solved until 1976 by Kenneth Appel and Wolfgang Haken. The four color theorem states that every map can be colored by using at most four colors. For a map, we can transform it into a graph, called a planar graph in order to make it easier to studied and proved. According to the four color theorem, a planar graph is 4-colorable. In other words, a graph with neither K4-minor nor K3,3-minor is 4-colorble. Hadwiger's conjecture is a generalization of the four color theorem. Hadwiger's conjecture states that a graph with no Kt+1-minor is t-colorable. In this research report, we first study the four color theorem and all results related to Hadwiger's conjecture. Then we prove that an inflation of n-graphs with n ≤ 7 satisfying the Hadwiger's conjecture.
URI:	https://rsuir-library.rsu.ac.th/handle/123456789/2747
metadata.dc.type:	Other
Appears in Collections:	ICT-Research

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.