王玥, 孫磊

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

圖多彩染色中的2度點(diǎn)刪除問(wèn)題

王玥, 孫磊*

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

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

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

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

1 主要結(jié)果

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

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

引理1.3[2]令n≥3為整數(shù)，設(shè)Cn為n個(gè)頂點(diǎ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

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

王玥(1991—), 女, 研究生, 研究方向?yàn)閳D論與組合優(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