寶石方塊與圖的著色理論 3 ~ Conjucture and More Extension

回到寶石方塊的問題 , 我在沒有足夠的證據下 , 提出下列疑問

If G is a Grid Graph n x n' and m < max{n , n'} => XS(G , P3) = ??


我目前已知 :
若 G is Grid Graph 8 x 7 則 XS(G, P3) ≧ 7 (請參考右圖)
但我有一個關於 m-coloring for Pn 的直觀看法的猜想
X(G,Pn) ≤ X(G,Pm) for n > m



上面這個敘述是不是更可以推廣到如下

If H' is the subgraph of H then X(G,H) ≤ X(G,H')

看似合理的推測 , 但要是問我為什麼 , 我大概用一句話回答
"在越大的子圖產生不會完全同色的情形 , 則自然需要越少的顏色來區分 , 因為我們只需其中一點塗不同色 , 也就是你越可容許更多相同顏色的點佈滿在該越大的子圖其餘點上"
但我相信這需要嚴謹且繁複的証明 , 在這只是漫談的Blog我就不贅述 , 不過或許各位會發現 , 我並沒有對更廣義的 X(G , H ) for H is a subgraph of G 去作定義 , 我在上一篇的那一連串定義只是H=Pn 的情形主要是為了解決寶石方陣在P_3的情形 , 廢話不多說 , 立刻給一個更廣義的著色理論數學定義 :

Def. Π(H) : V(H) -> {0 , 1}

Π(H) =Πd(x,y)=1 δ(x , y) 註:這是連乘

Def. (Coloring Extension to any subgraph H) C(G,H): V(G) -> N={0 , 1 , 2 ...m-1} is a m-coloring for H in G satisfying as follow: for all subgraph H ⊆ G 則 Π(u,v) = 0 and we denote the |C(G,H)| =m

Def. (Chromatic Number For Coloring Extension to any subgraph H) 我們把在Pn子圖上不能同時同色推廣至任意子圖上 ,
X(G , Pn) = min { |C(G,H)| = m | C(G,H) is a m-coloring for H in G}


舉個例子:

G=K4 , H = C3

則 X(K4 , C3) = 2 著色方式如上方小圖 , 圖中任意C3 subgraph 都不會同時塗相同顏色

附帶一提 , 將著色問題推廣至所有子圖 , 並非空穴來風 , 起因我最近思考的MIMO通訊問題中有關發收訊號群如何將他們的出現機率最大的雜訊做最離散的分布!!

嗯....問題敘述到此 , 我可以想像 , 會不會有個數學高手跳出來只著我的鼻子說 : "你真夠愚蠢 !! 難道你看不出來嗎 ? 這個問題有什麼好談的 , 因為它的難度是跟原本一般的Chromatic Number著色問題難度相同 , 懂不懂呀 !! 外行人......"

(複雜度猜想)~~~~~~~~~
OK !! 為了避免淪落成"外行人" , 即使本老爺的部落格也應該沒多少台灣數學好手會觀賞 , 但我還是先來個防禦性猜想吧

Computation Complexity of X(G,H) = Computation Complexity of X(G,P2) !?

沒錯!!要是有演算法分析的高手可以透過問題轉嫁的方式來說明上述這句話為真 , 真的要給她拍拍手 , 但拍拍手之外還不要高興太早 , 不要忘了 X(G,P2)就是原本一般兩點相連不同色的問題 , 在沒有特定的圖之下 , 已經被證實是NP-Complete , 哀哉呀!! 但我仍堅信 , 考慮Swap這個動作~XS(G,Pn) , 也就是我原本對寶石方陣的問題 , 絕對是相當相當困難的 , 我至今對他沒有太多想法...........