反極圖問題

反極圖問題(inverse extremal problem)是圖論的一個重要問題,指由極圖序列反求常用圖類的問題。

具體地說,對於一個給定的圖序列{sn, },反求對應於{S叫的禁用圖類,使{s,.,}是對於它的一個極圖序列的問題.對於充分大的m,一個禁用圖類丫以圖蘭圖Tn,。為極圖的充分必要條件是:存在L E `},以及1.上一條邊‘,使得X(L-e)=SG(T)=n,其中,X和必分別表示色數與次色數.進而,若對無窮多個n的值1',n,。是丫的極圖,則對充分大的m,它是對於獷的惟一的極圖.以上結論,就是所謂的T,,定理.

相關詞條

熱門詞條

聯絡我們