不含某些圖作為導出子圖的圖的色數

段 芳

（新疆師范大學數學科學學院，新疆烏魯木齊830054）

不含某些圖作為導出子圖的圖的色數

段 芳

（新疆師范大學數學科學學院，新疆烏魯木齊830054）

Erodo¨s證明了對于任意一個圖G，χ（G）－ω（G）可以任意大。因此，對一般圖而言，其色數不一定能找到一個與團數有關的上界。文章主要討論一類特殊的F－free圖的色數和團數的關系。設圖G＝（V，E）是一個不含K1，k+1+e、C4和C4+e為導出子圖的連通圖，不是星圖和奇圈。若α（G）≥k≥3，則χ（G）≤（k（k－1）／2）ω（G）。

色數；團數；F－free圖

文章只考慮不含環和重邊的有限無向圖。給定一個圖G＝（V（G），E（G）），用｜V（G）｜表示圖G中點的個數，稱為圖G的階數，用n來表示。取S是V（G）的一個非空子集，稱點集為S，S中的點相鄰當且僅當它們在圖G中相鄰的圖為S在圖G中的導出子圖，記為G［S］。若G［S］中沒有邊，則稱S是獨立集；若G［S］是完全圖，則稱S是團。圖G最大獨立集中點的個數稱為獨立數，用α（G）表示；圖G的最大的團中所含點的個數稱為團數，用ω（G）表示。如果圖G的點集可以劃分成k個獨立集，則稱k的最小取值為圖G的色數，記為χ（G）。另外，用G－S表示在圖G中去掉點集S中的所有點以及與點集S中的點所關聯的所有邊得到的圖。

早在七十年代，Chartrand等人在文獻［1］中就提出了不含某些圖作為導出子圖的圖的概念：對于給定的一些圖構成的集合F，若圖G不包含與集合F中任一圖同構的導出子圖，稱圖G是不含某些圖作為導出子圖的圖。特別的，當k＝1且H1＝K1，3時，圖G稱為無爪圖。這類圖倍受大家關注，有很多這方面的結論。如：文獻［3］和［5］中分別得到了不含K1，4和K1，4+e作為導出子圖的圖的一些結果。文獻［6］中得到clawfree圖的一些結果。……