关于图的路色数

ON THE PATH-CHPOMATIG NUMBER OF GRAPHS

本文证明了P_∞-K-临界图的一些简单性质,并给出了某些图类的路色数。主要证明了:(1)若x(G,P_∞)=K,则G包含一个P_∞-l-临界子图,这里对所有的l≤K;(2)设G是P_∞-K-临界图,H是G的子图,且H∈P_∞。,则x(G—H,P_∞)=K-1;(3)设T为m阶树,C_n为偶圈,则x(T×C_n,P_∞)=2;(4)若C_n为奇圈,则对任意树T,有x(T×C_n,P_∞)≤3;(5)若m≠n,则x(K_m×K_n,P_∞)=max{[(m+1)/2],[(n+1)/2]}。

This paper gives some simple properties of P∞-K-Critical graph and the Path-chromatic-numbers of some graphs, the following results are proved; (1)if x(G,P∞)=K, then G contains a P-1-critical subgraph,where l<k. (2)If G is a P∞-K-critical graph, H is a subgraph of G,H∈P∞ then x(G-H, P∞) = K-1. (3)If T is a m-order tree,Cn is a even cycle, then x(T×Cn, P∞) = 2.(4)If T is a m-order tree,Cn is a odd cycle, then x(T×Cn, P∞) <3. (5)if m≠n,then x(Km×Kn,P∞) = max{[(m + 1) /2], [(n+1)/2]}.