A note on total colorings of planar graphs without 4-cycles

Ping Wang; Jian-Liang Wu

Discussiones Mathematicae Graph Theory (2004)

  • Volume: 24, Issue: 1, page 125-135
  • ISSN: 2083-5892

Abstract

top
Let G be a 2-connected planar graph with maximum degree Δ such that G has no cycle of length from 4 to k, where k ≥ 4. Then the total chromatic number of G is Δ +1 if (Δ,k) ∈ {(7,4),(6,5),(5,7),(4,14)}.

How to cite

top

Ping Wang, and Jian-Liang Wu. "A note on total colorings of planar graphs without 4-cycles." Discussiones Mathematicae Graph Theory 24.1 (2004): 125-135. <http://eudml.org/doc/270290>.

@article{PingWang2004,
abstract = {Let G be a 2-connected planar graph with maximum degree Δ such that G has no cycle of length from 4 to k, where k ≥ 4. Then the total chromatic number of G is Δ +1 if (Δ,k) ∈ \{(7,4),(6,5),(5,7),(4,14)\}.},
author = {Ping Wang, Jian-Liang Wu},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {total coloring; planar graph; list coloring; girth; chromatic number},
language = {eng},
number = {1},
pages = {125-135},
title = {A note on total colorings of planar graphs without 4-cycles},
url = {http://eudml.org/doc/270290},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Ping Wang
AU - Jian-Liang Wu
TI - A note on total colorings of planar graphs without 4-cycles
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 1
SP - 125
EP - 135
AB - Let G be a 2-connected planar graph with maximum degree Δ such that G has no cycle of length from 4 to k, where k ≥ 4. Then the total chromatic number of G is Δ +1 if (Δ,k) ∈ {(7,4),(6,5),(5,7),(4,14)}.
LA - eng
KW - total coloring; planar graph; list coloring; girth; chromatic number
UR - http://eudml.org/doc/270290
ER -

References

top
  1. [1] J.A. Bondy and U.S.R. Murty (Graph Theory with Applications, North-Holland, 1976). 
  2. [2] O.V. Borodin, On the total coloring of planar graphs, J. Reine Angew. Math. 394 (1989) 180-185, doi: 10.1515/crll.1989.394.180. Zbl0653.05029
  3. [3] O.V. Borodin, A.V. Kostochka and D.R. Woodall, Total colorings of planar graphs with large maximum degree, J. Graph Theory 26 (1997) 53-59, doi: 10.1002/(SICI)1097-0118(199709)26:1<53::AID-JGT6>3.0.CO;2-G Zbl0883.05053
  4. [4] O.V. Borodin, A.V. Kostochka and D.R. Woodall, Total colourings of planar graphs with large girth, European J. Combin. 19 (1998) 19-24, doi: 10.1006/eujc.1997.0152. Zbl0886.05065
  5. [5] O.V. Borodin, A.V. Kostochka and D.R. Woodall, List edge and list total colourings of multigarphs, J. Combin. Theory (B) 71 (1997) 184-204, doi: 10.1006/jctb.1997.1780. Zbl0876.05032
  6. [6] J.L. Gross and T.W. Tucker (Topological Graph Theory, John and Wiley & Sons, 1987). 
  7. [7] A.J.W. Hilton, Recent results on the total chromatic number, Discrete Math. 111 (1993) 323-331, doi: 10.1016/0012-365X(93)90167-R. Zbl0793.05059
  8. [8] T.R. Jensen and B. Toft (Graph Coloring Problems, John Wiley & Sons, 1995). 
  9. [9] Peter C.B. Lam, B.G. Xu, and J.Z. Liu, The 4-choosability of plane graphs without 4-cycles, J. Combin. Theory (B) 76 (1999) 117-126, doi: 10.1006/jctb.1998.1893. Zbl0931.05036
  10. [10] A. Sanchez-Arroyo, Determining the total coloring number is NP-hard, Discrete Math. 78 (1989) 315-319, doi: 10.1016/0012-365X(89)90187-8. Zbl0695.05023
  11. [11] H.P. Yap, Total colourings of graphs, Lecture Notes in Mathematics 1623 (Springer, 1996). Zbl0839.05001

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.