structural graph theory and eifficient algorithm for graph coloring problems

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

In this research, we have worked on graph coloring problem for1. graphs on a surface, and 2. minor-closed family of graphs.Concerning the first one, we give several algorithmic results. Namely. we give a polynomial time algorithm for deciding 5-list-colorability of graphs on a fixed surface, and for deciding 3-list-colorablity of graphs of girth five on a fixed surface. Concerning the second one, we show that minimal-counterexample to the famous Hadwiger's conjecture is 0.2k-connected for the case k. This is the first step toward a chacterization of such a minimal-counterexample.