n-可着色图的一个充要条件

A Necessary and Sufficient Condition for n-Colorable Graphs

本文从完全图K_n出发,递归定义了非n色基本子图,n色同色元和n色异色元等概念,然后,给出了n-可着色图的一个充要条件:图G是n-可着色的当且仅当G不包含非n色基本子图。本文又得到一个结论:G是非n-1色基本子图当且仅当G是n-边临界图,从而给出了n-边临界图的构造。

Starting from complete graph K., in this paper we give by recursive method the definitions of non-n-chromatic elementary subgraph, n-chromatic single color element and n-chromatic different color element. Then a necessary and sufficient condition for n-colorable graphs is given as follows: Graph G is n-colorable if and only if G contains no non-n-chromatic elementary subgraph. This paper provides another conclusion: G is a non-(n—1)-chromatic elementary subgraph if and only if G is a n-edge critical graph. This result gives the construction of the n-edge critical graphs.