본문 바로가기
KERD
논문KCI 등재

Total colorings of planar graphs with maximum degree at least 7 and without adjacent 5-cycles

Xiang Tan
대한수학회 (The Korean Mathematical Society)|2016.01|대한수학회보 (Bulletin of the KMS)|제53권 제1호|pp. 139-151

0

조회

0

다운로드

0

인용

0

참고문헌

키워드

total coloringplanar graphadjacent 5-cycle
주제분류수학

초록

A $k$-total-coloring of a graph $G$ is a coloring of $V\cup E$ using $k$ colors such that no two adjacent or incident elements receive the same color. The total chromatic number $\chi''(G)$ of $G$ is the smallest integer $k$ such that $G$ has a $k$-total-coloring. Let $G$ be a planar graph with maximum degree $\Delta$. In this paper, it's proved that if $\Delta\geq 7$ and $G$ does not contain adjacent 5-cycles, then the total chromatic number $\chi''(G)$ is $\Delta+1$.

Abstract

A $k$-total-coloring of a graph $G$ is a coloring of $V\cup E$ using $k$ colors such that no two adjacent or incident elements receive the same color. The total chromatic number $\chi''(G)$ of $G$ is the smallest integer $k$ such that $G$ has a $k$-total-coloring. Let $G$ be a planar graph with maximum degree $\Delta$. In this paper, it's proved that if $\Delta\geq 7$ and $G$ does not contain adjacent 5-cycles, then the total chromatic number $\chi''(G)$ is $\Delta+1$.

참고문헌 (24)

  1. M. Behzad, "Graphs and their chromatic numbers", Ph.D., pp.1965
  2. J. A. Bondy, "Graph Theory with Applications" (1976), North-Holland
  3. O. V. Borodin, "Total colorings of planar graphs with large maximum degree", J. Graph Theory, 26(1), pp.53~59 (1997)
  4. O. V. Borodin, "Total colorings of planar graphs with large girth", Europ. J. Combinatorics, 19, pp.19~24 (1998)
  5. J. S. Cai, "Total coloring of a planar graph without 7-cycles with chords", Acta Math. Appl. Sin, 37(2), pp.286~296 (2014)
  6. G. J. Chang, "Local condition for planar graphs of maximum degree 7 to be 8-totally-colorable", Discrete Appl. Math, 159(8), pp.760~768 (2011)
  7. J. Chang, "Total colorings of planar graphs with maximum degree 8 and without 5-cycles with two chords", Theoret. Comput. Sci, 476, pp.16~23 (2013)
  8. D. Z. Du, "Planar graphs with maximum degree 8 and without adjacent triangles are 9-totally colorable", Discrete Appl. Math, 157(13), pp.2778~2784 (2009)
  9. J. F. Hou, "Total colorings of planar graphs without 6-cycles", Discrete Appl. Math, 159(2-3), pp.157~163 (2011)
  10. A. V. Kostochka, "The total chromatic number of any multigraph with maximum degree five is at most seven", Discrete Math, 162(1-3), pp.199~214 (1996)
  11. L. Kowalik, "Total-Coloring of plane graphs with maxi-mum degree nine", SIAM J. Discrete Math, 22(4), pp.1462~1479 (2008)
  12. D. P. Sanders, "On total 9-coloring planar graphs of maximum degree seven", J. Graph Theory, 31(1), pp.67~73 (1999)
  13. L. Shen, "On the 7-total colorability of planar graphs with maximum degree 6 and without 4-cycles", Graphs Combin, 25(3), pp.401~407 (2009)
  14. J. J. Tian, "Total colorings of planar graphs without adjacent chordal 5-cycles", Util. Math, 91, pp.13~23 (2013)
  15. V. G. Vizing, "Some unresolved problems in graph theory", Uspekhi Mat. Nauk, 23, pp.117~134 (1968)
  16. B. Wang, "Total colorings of planar graphs without intersecting 5-cycles", Discrete Appl. Math, 160(12), pp.1815~1821 (2012)
  17. B. Wang, "Total colorings of planar graphs with maximum degree seven and without intersecting 3-cycles", Discrete Math, 311(18-19), pp.2025~2030 (2011)
  18. H. J. Wang, "Total colorings of planar graphs without adjacent 4-cycles", Discrete Math, 312(11), pp.1923~1926 (2012)
  19. H. J. Wang, "Total coloring of planar graphs with maximum degree 8", Theoret. Comput. Sci, 522, pp.54~61 (2014)
  20. H. J. Wang, "Minimum total coloring of planar graph", J. Global Optim, 60(4), pp.777~791 (2014)
  21. P. Wang, "A note on total colorings of planar graphs without 4-cycles", Discuss. Math. Graph Theory, 24(1), pp.125~135 (2004)
  22. W. Wang, "Total chromatic number of planar graphs with maximum degree ten", J. Graph Theory, 54(2), pp.91~102 (2007)
  23. Y. Q. Wang, "Plane graphs with maximum degree 7 and without 5-cycles with chords are 8-totally-colorable", Sci. China Math, 41(1), pp.95~104 (2011)
  24. H. P. Yap, "Total colourings of graphs, Lecture Notes in Mathematics", pp.1623~ (1996), Springer

관련 논문AI추천

LIST EDGE AND LIST TOTAL COLORINGS OF PLANAR GRAPHS WITHOUT 6-CYCLES WITH CHORDAijun Dong, Guizhen Liu, Guojun Li대한수학회 · 대한수학회보2012 · 제49권 제2호A sufficient condition for acyclic 5-choosability of planar graphs without 5-cyclesLin Sun대한수학회 · 대한수학회보2018 · 제55권 제2호List injective coloring of planar graphs with girth at least fiveHong-Yu Chen대한수학회 · 대한수학회보2024 · 제61권 제1호THE LINEAR 2-ARBORICITY OF PLANAR GRAPHS WITHOUT ADJACENT SHORT CYCLESHong-Yu Chen, Jian-Liang Wu, Xiang Tan대한수학회 · 대한수학회보2012 · 제49권 제1호A proper total coloring distinguishing adjacent vertices by sums of some product graphs김동석, 이성진, 최하나, YEONHEE LEE대한수학회 · 대한수학회논문집2015 · 제30권 제1호On the conjecture of planar graphsAbdollahzadeh Ahangar, Pushpalatha장전수학회 · Advanced Studies in Contemporary Mathematics2010 · 제20권 제1호

이 간행물의 다른 논문 (22건)

On nonlinear polynomial selection and geometric progression (mod $N$) for number field sieve권순학, Namhun Koo, 조국화pp. 1-20On some root behaviors of certain sums of polynomials김선홍, Han-Kyol Chongpp. 21-28Value distribution of some $q$-difference polynomialsNa Xu, Chun-Ping Zhongpp. 29-38Semi-asymptotic non-expansive actions of semi-topological semigroupsAlireza Medghalchi, Massoud Aminipp. 39-48Shared values and Borel exceptional values for high order difference operatorsJie Zhang, Liangwen Liaopp. 49-60
원문 보기