不含某些圖作為導(dǎo)出子圖的圖的色數(shù)

段 芳

（新疆師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，新疆烏魯木齊830054）

不含某些圖作為導(dǎo)出子圖的圖的色數(shù)

段 芳

（新疆師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，新疆烏魯木齊830054）

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

色數(shù)；團(tuán)數(shù)；F－free圖

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

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

圖的色數(shù)、團(tuán)數(shù)和獨(dú)立數(shù)有密切的關(guān)系，對任意圖G，很容易看出χ（G）≥ω（G）且χ（G）≥但對一般圖而言，其色數(shù)不一定能找到一個(gè)與團(tuán)數(shù)相關(guān)的上界。對于很多不含四個(gè)點(diǎn)的圖作為導(dǎo)出子圖的圖類，已有色數(shù)與團(tuán)數(shù)有關(guān)的一些結(jié)果：Chudnovsky和Seymour在文獻(xiàn)［2］中證明了如果G是一個(gè)α（G）≥3的無爪圖，則χ（G）≤2ω（G）。文獻(xiàn)［7］中證明了對不含K1+P3和C5作為導(dǎo)出子圖的圖G，有χ（G）≤ω；文獻(xiàn)［4］中證明了如果G是一個(gè)不含2K1+K2和C5作為導(dǎo)出子圖的圖，若ω（G）＝2，則χ（G）＝ω（G）；若ω（G）≥3，那么χ（G）≤2ω（G）32。文章將在特殊的圖類上討論這個(gè)問題。

令圖C4+e表示將圈C4中的兩個(gè)度為2的點(diǎn)連接而得到的圖。文章證明了當(dāng)α（G）≥k≥3時(shí)，若圖G是一個(gè)連通的不含K1，k+1+e、C4和C4+e作為導(dǎo)出子圖的圖，那么χ（G）≤（k（k－1）／2）ω（G）。

1 主要結(jié)論

在下面的證明中，用符號(hào)NG（v）表示點(diǎn)v∈V（G）在圖G中所有鄰點(diǎn)構(gòu)成的集合。

定理 圖G＝（V（G），E（G））是一個(gè)不含K1，k+1+e、C4和C4+e作為導(dǎo)出子圖的連通圖，不是星圖，也不是奇圈。若α（G）≥k≥3，則χ（G）≤（k（k－1）／2）ω（G）。

證明 圖G不是奇圈，又因?yàn)棣粒℅）≥k≥3，所以圖G不是完全圖。因此由Brook定理可以得到χ（G）≤Δ（G）。如果要證明χ（G）≤（k（k－1）／2）ω（G），只需要證明Δ（G）≤（k（k－1）／2）ω（G）即可。

下面通過對圖G的點(diǎn)數(shù)｜V（G）｜進(jìn)行歸納來證明這個(gè)結(jié)論。取點(diǎn)v是圖G中一個(gè)度為Δ（G）的點(diǎn)。因?yàn)棣粒℅）≥k，如果V（G）＼｛v｝中所有的點(diǎn)都和點(diǎn)v相鄰，那么點(diǎn)v至少有k個(gè)互不相鄰的鄰點(diǎn)，不妨設(shè)這些鄰點(diǎn)所構(gòu)成的點(diǎn)集為A＝｛a1，a2，…，ak｝。又因?yàn)閳DG不是星圖，因此至少存在一個(gè)不屬于集合A的點(diǎn)u，使得點(diǎn)u至少和集合A中某一個(gè)點(diǎn)相連。下證點(diǎn)u只能和集合A中一個(gè)點(diǎn)相連。否則，若點(diǎn)u和A中兩個(gè)點(diǎn)ai和aj都相鄰，那么圖G［u，v，ai，aj］導(dǎo)出了圖C4+e，與已知條件矛盾。但若u只和A中一個(gè)點(diǎn)ai連接，那么圖G［u，v，a1，…，ak］又導(dǎo)出了子圖K1，k+1+e，與已知條件矛盾。因此在V（G）＼｛v｝中不是所有的點(diǎn)都和點(diǎn)v相鄰，可設(shè)存在一個(gè)點(diǎn)w∈V（G），w≠v且w和v不相鄰。這時(shí)總可以選擇點(diǎn)w使得G－｛w｝是連通的（只需要選擇一個(gè)距離點(diǎn)v最大的點(diǎn)即可）。且顯然有α（G－｛w｝）≥k－1。

如果α（G－｛w｝）≥k，那么根據(jù)歸納假設(shè)得到Δ（G－｛w｝）≤（k（k－1）／2）ω（G－｛w｝）。顯然有ω（G－｛w｝）≤ω（G），又因?yàn)閣和v不相鄰，所以Δ（G）＝Δ（G－｛w｝）。這時(shí)Δ（G）＝Δ（G－｛w｝）≤（k（k－1）／2）ω（G－｛w｝）≤（k（k－1）／2）ω（G），得證。

因此下面可以假設(shè)α（G－｛w｝）＝k－1。令集合A＝｛a1，a2，…，ak－1｝?V（G－｛w｝）是圖G－｛w｝的獨(dú)立集。取集合Ni＝NG－｛w｝（ai），集合Mi＝Ni＼（∪j≠i，1≤j≤k－1Nj），這里i＝1，2，…，k－1。且令集合Mij＝Ni∩Nj，這里1≤i，j≤k－1，i≠j。因?yàn)橐阎粒℅－｛w｝）＝k－1，所以圖G－｛w｝中每一個(gè)點(diǎn)要么在獨(dú)立集A中，要么在某一個(gè)點(diǎn)集Ni中。下面可證G［Mi∪｛ai｝］是一個(gè)團(tuán)。用反證法，如果在Mi中存在兩個(gè)點(diǎn)x，y不相鄰，那么點(diǎn)集｛x，y｝∪A＼ai就是G－｛w｝中一個(gè)點(diǎn)數(shù)為k的獨(dú)立集，與條件α（G－｛w｝）＝k－1矛盾。因此G［Mi∪｛ai｝］是一個(gè)團(tuán)。

特別的，如果取k＝2，可以得到如下推論。

推論 圖G＝（V，E）是一個(gè)不含K1，3+e、C4和C4+e作為導(dǎo)出子圖的連通圖，不是星圖，也不是奇圈。若α（G）≥k≥3，則χ（G）≤ω（G）。

參考文獻(xiàn)：

［1］G.Chartrand，D.Geller and S.Hedetniemi，Graphs with Forbidden Subgraphs［M］.J.Combin.Theory，1971，（10）：12－41.

［2］Maria Chudnovsky and Paul Seymour.Claw－free graphs VII.Colouring clawfree graphs［M］.Manuscript，2004.

［3］F.Duan，G.Wang，Note on the longest paths in｛K1，4，K1，4+e｝－free graphs［J］.Acta Math.Sinica，2012，28：2501－2506.

［4］F.Duan，Baoyin.Wu.On chromatic number of graphs without certain induced subgraphs［M］.Ars combinatoria，2011，6：33－44.

［5］R.Li，Hamiltonicity of 2－connected｛K1，4，K1，4+e｝－free graphs［J］.Discrete Math，2004，287：69－76.

［6］T.Runli and X.Liming，On hamiltonicity of 2－connected claw－free graphs［J］.Appl.Math.J.Chinese Univ，2012，（27）：234－242.

On Chromatic Number of Graphs without Certain Induced Subgraphs

DUAN Fang
（School of Mathematical Sciences，Xinjiang Normal University，Urumqi，Xinjiang，830054，China）

In general，there is no upper bound on the chromatic number of a graph in terms of its clique num?ber，since by a classical result of Erodo¨swe know that the differenceχ（G）－ω（G）can be arbitrarily large.In this thesis，we shall focus on F－free graphs and obtain results that the chromatic number of F－free graphs has upper bound in terms of their clique number。LetG be a｛K1，k+1+e，C4，C4+e｝－free graph，if α（G）≥k≥3，then χ（G）≤（k（k－1）／2）ω（G）.

Clique number；Chromatic number；F－free graph

O157.5

A

1008?9659（2015）01?0022?03

2014－11－30

段 芳（1979－），女，遼寧大連人，碩士，主要從事圖論方向的教學(xué)與研究。