图多彩染色中的2度点删除问题

王玥, 孙磊

(山东师范大学数学与统计学院，山东 济南 250014)

图多彩染色中的2度点删除问题

王玥, 孙磊*

(山东师范大学数学与统计学院，山东 济南 250014)

多彩染色；多彩色数；2度点

图的多彩染色是在图的正常染色的基础上对任一点的邻点的颜色种类添加限制，使得邻点的颜色种类要不小于邻点个数和r的最小值.

本文给出了图G删掉任意一个2度点后r-多彩染色数变化的界。

1 主要结果

Montgomery[6]证明了在图G中删去任意一个点后动态染色数变化的界的相关结果。

注意到这里只研究了r=2时动态染色的变化情况。当r为更一般的值时，考虑在图G中删掉一个2度点后，r-多彩染色数的变化。在证明定理之前先介绍几个引理。

引理1.3[2]令n≥3为整数，设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

国家自然科学基金(11271365); 山东省自然科学基金(ZR2014JL001)

王玥(1991—), 女, 研究生, 研究方向为图论与组合优化。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