圖多彩染色中的2度點刪除問題

王玥, 孫磊

(山東師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，山東 濟南 250014)

圖多彩染色中的2度點刪除問題

王玥, 孫磊*

(山東師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，山東 濟南 250014)

多彩染色；多彩色數(shù)；2度點

圖的多彩染色是在圖的正常染色的基礎(chǔ)上對任一點的鄰點的顏色種類添加限制，使得鄰點的顏色種類要不小于鄰點個數(shù)和r的最小值.

本文給出了圖G刪掉任意一個2度點后r-多彩染色數(shù)變化的界。

1 主要結(jié)果

Montgomery[6]證明了在圖G中刪去任意一個點后動態(tài)染色數(shù)變化的界的相關(guān)結(jié)果。

注意到這里只研究了r=2時動態(tài)染色的變化情況。當(dāng)r為更一般的值時，考慮在圖G中刪掉一個2度點后，r-多彩染色數(shù)的變化。在證明定理之前先介紹幾個引理。

引理1.3[2]令n≥3為整數(shù)，設(shè)Cn為n個頂點的圈，若r≥2，則有

證明完畢。

2 例子

[1]BONDYJA,MURTYUSR.Graphtheorywithapplications[M].NewYork,Elsevier：1976.

[2]LAIHJ,LINJL,MONTGOMERYB,etal.Conditionalcoloringsofgraphs[J].DiscreteMathematics, 2006, 306(16): 1997-2004.

[3]CHENY,FANSH,LAIHJetal.Ondynamiccoloringforplanargraphandgraphsofhighergenus[J].DiscreteApplMath, 2012, 160: 1064-1071.

[4]LAIHJ,MONTGOMERYB,POONH.Upperboundsofdynamicchromaticnumber[J].ArsCombinatoria, 2003, 68: 193-201.

[5]KIMSJ,LEESJ,PARKWJ.Dynamiccoloringandlistdynamiccoloringofplanargraphs[J].DiscreteApplMath, 2013, 161(13/14): 2207-2212.

[6]MONTGOMERYB.Dynamiccoloring[M].Morgantown:WestVirginiaUniversity, 2001.

[7]MIAOLY,LAIHJ,GUOYF,etal.Elementdeletionchangesindynamiccoloringofgraphs[J].DiscreteMathematics, 2016, 339(5): 1600-1604.

DOI:10.3976/j.issn.1002-4026.2017.01.016

Studieson2-vertexdeletionissuesinr-huedcoloringofgraphs

WANGYue,SUNLei*

(SchoolofMathematicsandstatistics,ShandongNormalUniversity,Jinan250014,China)

∶r-huedcoloring； r-huedchromaticnumber； 2-vertex

2016-05-06

國家自然科學(xué)基金(11271365); 山東省自然科學(xué)基金(ZR2014JL001)

王玥(1991—), 女, 研究生, 研究方向為圖論與組合優(yōu)化。E-mail:moon875@qq.com

*通信作者，孫磊(1971—), 女, 博士, 副教授。E-mail:lsun89@163.com

O

A

1002-4026(2017)02-0095-03

10.3976/j.issn.1002-4026.2017.01.017