边着色路到完全图的嵌入

AN EMBEDDING OF EDGE-COLOURED PATHS IN THE COMPLETE GRAPHS

一、一个猜想设 P_n 为具有 n 个顶点的一条路,它的 n-1条边着上了不同的颜色,若这个着色能扩充为 n 个顶点的完全图 K_n 的一个正常的 x′(K_n)一边着色,则称边着色路 P_n 能嵌入于完全图.一般说来,设 G 是具有边色数 x′(G)的一个简单图,令 M(G)为 G 中所有满足以下性质的子图 H(?)G 的集合:存在 G 的一种正常的 x′(G)-边着色使得 H 的各条边具有不同的颜色.设 K_n 是 n 个顶点的完全图,把集合 M(K_n)简记为 M_n 于是我们一开始提出的问题“P_n 能否嵌入于完全图”等价于“P_n 是否属于 M_n”.

Let P_n be the path with n vertices whose edges are coloured with distinct colo-ures.Let G be a simple graph with edge-chromatic index X′(G).Define M(G)tobe the set of all subgraphs H(?)G such that there exists a X′(G)-edge colouring ofG with each edge of H receiving a different colour.We denote M(K_n)by M_n,where K_n is a complete graph with n vertices.In 1986,A.Hartman[1]posed thefollowing conjecture:P_n∈M_n, for all n(?)4,6.We call that the problem is anenbedding of the edge-coloured paths in the complete graphs.In this paper we haveobtained a necessary and sufficient condition for the family of 2-elements subsets tohave a system of distinct representatives and constructed a special class of Latinsquares,then the conjecture is true.