次色數

次色數(subchromatic number)圖論的基本概念之一指給定的禁用圖類獷中所有圖的色數最小值與1的差.禁用圖類了的次色數記為}G(.}).禁用圖類丫的分解是指有如下性質的圖M組成的集合:設羅的次色數為p，對於丫中一個圖L,M是L的一個導出子圖，且從L中去掉所有M的節點和它們的關聯邊所得的圖是(p-1)可著色的.所謂分解定理是指如下結論:設禁用圖類丫的次色數為p,}的分解為產，則每個n階極圖GEEx(n,})可由適當的完全p部圖Kn} ,，改變O(ex(n,川)即ex(n,})/n的常數倍條邊得到.這裡n; (n/p)+O(ex(n，})/n)， 8(G)=(1一p- 1)n+O(ex(n,})/n)，占(G，)表示G，中節點的最小次.