mycielski图的染色问题(编辑修改稿)

mycielski图的染色问题(编辑修改稿)内容摘要：

时有 39。 ( ( )) 4npMC  . 定理 3[5] 对 1p 阶的轮图 pW ,有 39。 7 , 3。 ( ( ) )2 , 4 .np pMW pp    定理 4[5] 对 1p 个点的星图 pS ,则有 39。 ( ( )) 2 , 1npM S p n . 定理 5[5] 对 1p 阶的扇 pF ,有 .1,2))((  npFM pn 7 定理 6[5] 完全二部图,mnK的广义 Mycielski 图记为,( ) , ( 1, 2)l m nM K l n m  .对图,()l mnMK, ( 2 , 1 , , , )n m l m n l N   ,有 39。 ,( ( )) 2 .l m nM K n  猜想 [5] 对简单图 G 及 1n , 39。 ( ( )) ( ( ))nnM G M G  ,其中 ()G 表示 G 的最大度 . (二 ) 邻强边色数 定义 4 [3] 对图 ( , )GVE , 若 一 正 常 染 色 f 满足 ( ) ( )Cu Cv , 其中( ) , ( ) { ( ) | }uv E G C u f uv uv E  ,则称 f 为 G 的邻强边染色法 ,简记作 k ASEC ,且称 39。 ( ) m i n{ | }as G k k AS ECG  of }G 为 G 的邻强边色数 . 1. Mycielski 图的邻强边色数 定理 1[3] 对 n 个点的路 nP , ( 2)n 39。 4 , 3( ( )) 5 , 2 , 4,5as nnPnnn 定理 2[3] 对圈 nC ,有 39。 5 , 3 , 4( ( )),5as n nP nn    定理 3[3] 对 1n 阶的轮图 nW ,有 39。 7 , 3( ( ))2 , 4as n nW nn    定理 4[3] 设 G 为阶不小于 1n 的星图 nS (即完全二部图 ,lnK ),则有 8 39。 5 , 1( ( ))2 , 2as n nF nn    定理 5[3] 对扇 nF ,有 39。 5 , 2( ( )) 7, 32 , 4as nnx S nnn 定理 6[3] 对完全图 nK ,有 39。 5 , 1( ( ) )2 1, 3a s n nK nn    Mycielski 图的邻强边色数 定理 1[1] 对 1p 阶的轮图 pW ，有 39。 7 , 3( ( ) )2 , 4as n p pMW pp    定理 2[5] 完全二部图 ,mnK 的广义 Mycielski 图记为 ,( ) , ( 1, 2)l m nM K l n m  . 对图 ,( ) , ( 1, 2)l m nM K l n m  ,有 39。 , 2,( ( ) ) 2 1 ,a s l m n n n mMK n n m    (三 ) 全色数 定义 5[6] 设 G 为简单图 ,映射  : ( ) ( ) {1 , 2 , ..., }V G E G k  满足 ( ) , ( ) ( )uv E G u v  。 9 , ( ) , ( ) ( )uv uw E G uv v w  。 则称  为 G 的 k 全染色 ,简记为 k TC,并称 ( ) m in{ |T Gk TC。