图的一个强染色问题

A Question of Strong Vertex Colouring

设G（V，E）是一个图，△（G）为图G中顶点的最大度．图G的一个k－染色f，若使得任意的两个距离小于等于2的顶点u，v满足f（u）≠f（v），则称f是G的k-强染色，并称Xs（G）＝min｛k：存在G的一件一强染色｝为强色数．对任意一个图G，是否存在常数C，使得■？，该问题是在99全国图论研讨会上提出来的．本文证明了对任意的常数C，都存在偶图G。

Let G(V, E) be a graph and A(G) be the largest degne of G. A colourin of G is strong if any two vertices u and v with d(u, v) < 2 have dishnct colours. The stron chromatic number, X.(G) of G is the minimum number k of colouring for which G' is k-strong -vertex-colourable. For any graph G, does there exist a constant C such tha Xs(G) < C△(G)?The question was raised on the National Graph Theory Conference in 1999- In this paper we prove that for any constant C, there exists a bipartite graph G such tha Xs(G) > C△(G).