图的色数与亏格的相对独立性

Relative Independence of Chromatic Number and Genus of Graph

本文先证明如下定理:“对于每一个非负整数p,亏格为p 的图的色数可以是任意整数m, 2≤m≤[7+(1+48p/2)].”然后,据此定理得结论:当m≥3,要找到m—色图的充分必要条件基本上是不可能的,即使不说根本不可能。

The following theorem has been proved in this paper:“For each non—negative integer p,thechromatic number of the graph of genus p can be any integer m,2≤m≤[(7+(1+48p)^(1/2)/2]It then leads to the conclusion that it is impossible to find out the sufficient and necessary condi-tion for m—chromation graph if m≥3.