Structures of graphs on surfaces with complete minors

点击翻译按钮获取中文摘要

This study deals with a problem : A given graph G on a fixed surface, which complete graph Kn does G have as a minor? This problem is difficult in general, and the problem combining this and graph coloring is well-known as Hadwiger's conjecture, one of the important open problems in the literature. In the research, restricting graphs on surfaces to be triangulations, we characterized the graphs on the orientable surface of genus up to 3 and the nonorientable surface of genus up to 4 containing K_6 as a minor. In order to do so, we used the complete list of irreducible triangulations on those surfaces and the theory for graph transformations.