摘要
本文从一个新的角度来研究有限、无向的简单图的色数,将图的顶点间的相邻关系表为若干个同余关系,给出了使它们的色数等于其最大团的顶点个数的两类图。
Let N={n_1,…,n_r} be a set of r positive integers, and for all i≠j in l≤i,J≤r, nn hold, and let M={m_1,… ,m_3} be a set of s distinct positive integers, we define G(N,M) to be the graph whose vertices set is M and m adjoin m_j iff there is some n_k∈N such that n_k(m_i— m_j), where l≤i≠j ≤s, then the following results are proved in this paper.Theorem 1 Let G be a finite simple graph, then there is a set N of distinct primes and another set M of distinct positive integers such that GG(N,M).Theorem 2 Let G=G(N,M), and let c(G) be the number of the vertices of the maximum clique of G, then the chromatic number of G is equal to c(G) if 2∈N or |N|=2.
出处
《吉林大学自然科学学报》
CAS
CSCD
1991年第4期30-32,共3页
Acta Scientiarum Naturalium Universitatis Jilinensis
关键词
图
色数
同余
简单图
graph, chromatic number, congruence
