Total Coloring of Planar Graphs Without Chordal Short Cycles

被引:0
作者
Huijuan Wang
Bin Liu
Jianliang Wu
机构
[1] Qingdao University,College of Mathematics
[2] Ocean University of China,Department of Mathematics
[3] Shandong University,School of Mathematics
来源
Graphs and Combinatorics | 2015年 / 31卷
关键词
Planar graph; Total coloring; Cycle;
D O I
暂无
中图分类号
学科分类号
摘要
Let G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document} be a planar graph with Δ≥8\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varDelta \ge 8$$\end{document} and v\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v$$\end{document} be a vertex of G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document}. It is proved that χ′′(G)=Δ+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\chi ''(G)=\varDelta +1$$\end{document} if v\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v$$\end{document} is not incident with chordal 5\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$5$$\end{document}- or 6\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$6$$\end{document}-cycles by Shen et al. (Appl Math Lett 22:1369–1373, 2009), or v\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v$$\end{document} is not incident with 2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2$$\end{document}-chordal 5\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$5$$\end{document}-cycle by Chang et al. (Theor Comput Sci 476:16–23, 2013). In this paper we generalize these results and prove that if v\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v$$\end{document} is not incident with chordal 6\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$6$$\end{document}-cycle, or chordal 7\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$7$$\end{document}-cycle, or 2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2$$\end{document}-chordal 5\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$5$$\end{document}-cycle, then χ′′(G)=Δ+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\chi ''(G)=\varDelta +1$$\end{document}.
引用
收藏
页码:1755 / 1764
页数:9
相关论文
共 36 条
[1]  
Borodin OV(1989)On the total coloring of planar graphs J. Reine Angew. Math. 394 180-185
[2]  
Chang GJ(2011)Local condition for planar graphs of maximum degree 7 to be 8-totally colorable Discrete Appl. Math. 159 760-768
[3]  
Hou JF(2009)Planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable Discrete Appl. Math. 157 2778-2784
[4]  
Roussel N(1996)The total chromatic number of any multigraph with maximum degree five is at most seven Discrete Math. 162 199-214
[5]  
Du DZ(2008)Total-coloring of plane graphs with maximum degree nine SIAM J. Discrete Math. 22 1462-1479
[6]  
Shen L(2011)Total colorings of planar graphs without 6-cycles Discrete Appl. Math. 159 157-163
[7]  
Wang YQ(2009)Total colorings and list total colorings of planar graphs without intersecting 4-cycles Discrete Math. 309 6035-6043
[8]  
Kostochka AV(2010)Total coloring of planar graphs of maximum degree eight Inf. Process. Lett. 110 321-324
[9]  
Kowalik L(1999)On total 9-coloring planar graphs of maximum degree seven J. Graph. Theory 31 67-73
[10]  
Sereni J-S(2009)Total colorings of planar graphs with maximum degree at least 8 Sci. China Ser. A 52 1733-1742