Series-Parallel图的全选择数与全色数.pdfVIP

第31卷第4期 河南大学学报(自然科学版) 丫oDfe3c::.0S0o14 2(101年 12月 JotanalofHe.-University(Naturalscinoe) Series-Parallel图的全选择数与全色数 李 涛 (南阳师范学院数学系，河南南阳373061) 摘 要:对2连通Series-Parallel图G,i正明了当△(引=4时 其全选择数等于.A((.)*l;在9(G),3时、其全色 数等十_I(G) 坛对,I(G)#3时，其边选择数等于其边色数(即列表染色猜想〕由十外平血ICI 特殊17 Series-panllel图本文包含了外平而图的相应染色结论 关键词:Seri-Parallel图;平面图;全染色 中图分类号:()157.5 文献标识码:A 文章编号:1003-4978(20()l)(t4-00374W OntheTotalandListTotalChromaticNumberof Series-ParallelGraphs 口 la( (Dr7,armuraofAfwh,,XwoongT,-hers College,?Vanyang473061，HenanChina) Abstract:Wesaythatasimplegraph ‘isaSeries-Parallelgraph,shortlySP卿沙 if‘doesnotcmrtain，subgaphluel曰‘ homeomorphictothecomplete4-graph.IhetotalchromaticnrrrnherofSPgraphs[,ereresearchedindrispaper.1}1G},一tSI graph.*provedthatthefisttotalchromaticmunberisequalto.}(匆+IifGis2-ronuecsedand-A苟?4,thetotaldr,oru,t numberisequalto6(G)+IifVG)?3,andlistedgeclaumaticnumberisequaltoitsedgechromatic，umlxrif-3rGr“ (e.g.ListColoringConjecture晚true)AsaclassofspecialSPgraphs,theconclusionisrolefurouterplanargrapll+ Keywords:Series-Parallelgraphs;planargmphs;totalcoloring 0 引言 对于平面图的全染色，Bonds和Murly提出1全色数不超过-}(G)+2的猜想}、’1989张忠辅=jAE明1 ‘为外平面图时猜想成立，且其全色数不超过。()‘、户.1989年，Borodin证明f当-A(G)不等十6.7,8时待 想成立 且当。()‘}14时其全色数不超过△(G)+1`t0 RHaggkcist等人于1992年提出7列表染色猜想1I(!,idColoringConjecture,简记LCC)若 ‘足某DIHih线 图则XL;G)二X(G)从而把点的列表染色问题引向边的列表染色 同时HHaggkist等人在夕{山研究r牛日 应的与、边— 全列表染色.目前，GFred证明了LCC对无环偶图成立圈，我们给出了外平而图的全达择数3‘， 但对其它甚至相当简单的图类，LCC及全列表色数问题均未解决 本文对乡P图证明J，当乙(‘)之4时其全选择数不超过。(‘、十1，蕴涵1其全色数不超过少 乙、，{;在 ,(G)}3时，证明了LCC成立，并把9〔J,[13，的结果推广到S-P图.关于S-P图染色的其它结果见文献[]I-