Edge-choosability and total-choosability of planar graphs with no adjacent 3-cycles

Daniel W. Cranston

Discussiones Mathematicae Graph Theory (2009)

  • Volume: 29, Issue: 1, page 163-178
  • ISSN: 2083-5892

Abstract

top
Let G be a planar graph with no two 3-cycles sharing an edge. We show that if Δ(G) ≥ 9, then χ'ₗ(G) = Δ(G) and χ''ₗ(G) = Δ(G)+1. We also show that if Δ(G) ≥ 6, then χ'ₗ(G) ≤ Δ(G)+1 and if Δ(G) ≥ 7, then χ''ₗ(G) ≤ Δ(G)+2. All of these results extend to graphs in the projective plane and when Δ(G) ≥ 7 the results also extend to graphs in the torus and Klein bottle. This second edge-choosability result improves on work of Wang and Lih and of Zhang and Wu. All of our results use the discharging method to prove structural lemmas about the existence of subgraphs with small degree-sum. For example, we prove that if G is a planar graph with no two 3-cycles sharing an edge and with Δ(G) ≥ 7, then G has an edge uv with d(u) ≤ 4 and d(u)+d(v) ≤ Δ(G)+2. All of our proofs yield linear-time algorithms that produce the desired colorings.

How to cite

top

Daniel W. Cranston. "Edge-choosability and total-choosability of planar graphs with no adjacent 3-cycles." Discussiones Mathematicae Graph Theory 29.1 (2009): 163-178. <http://eudml.org/doc/270180>.

@article{DanielW2009,
abstract = {Let G be a planar graph with no two 3-cycles sharing an edge. We show that if Δ(G) ≥ 9, then χ'ₗ(G) = Δ(G) and χ''ₗ(G) = Δ(G)+1. We also show that if Δ(G) ≥ 6, then χ'ₗ(G) ≤ Δ(G)+1 and if Δ(G) ≥ 7, then χ''ₗ(G) ≤ Δ(G)+2. All of these results extend to graphs in the projective plane and when Δ(G) ≥ 7 the results also extend to graphs in the torus and Klein bottle. This second edge-choosability result improves on work of Wang and Lih and of Zhang and Wu. All of our results use the discharging method to prove structural lemmas about the existence of subgraphs with small degree-sum. For example, we prove that if G is a planar graph with no two 3-cycles sharing an edge and with Δ(G) ≥ 7, then G has an edge uv with d(u) ≤ 4 and d(u)+d(v) ≤ Δ(G)+2. All of our proofs yield linear-time algorithms that produce the desired colorings.},
author = {Daniel W. Cranston},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {list coloring; edge coloring; total coloring; Vizing's Conjecture; Vizing's conjecture},
language = {eng},
number = {1},
pages = {163-178},
title = {Edge-choosability and total-choosability of planar graphs with no adjacent 3-cycles},
url = {http://eudml.org/doc/270180},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Daniel W. Cranston
TI - Edge-choosability and total-choosability of planar graphs with no adjacent 3-cycles
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 1
SP - 163
EP - 178
AB - Let G be a planar graph with no two 3-cycles sharing an edge. We show that if Δ(G) ≥ 9, then χ'ₗ(G) = Δ(G) and χ''ₗ(G) = Δ(G)+1. We also show that if Δ(G) ≥ 6, then χ'ₗ(G) ≤ Δ(G)+1 and if Δ(G) ≥ 7, then χ''ₗ(G) ≤ Δ(G)+2. All of these results extend to graphs in the projective plane and when Δ(G) ≥ 7 the results also extend to graphs in the torus and Klein bottle. This second edge-choosability result improves on work of Wang and Lih and of Zhang and Wu. All of our results use the discharging method to prove structural lemmas about the existence of subgraphs with small degree-sum. For example, we prove that if G is a planar graph with no two 3-cycles sharing an edge and with Δ(G) ≥ 7, then G has an edge uv with d(u) ≤ 4 and d(u)+d(v) ≤ Δ(G)+2. All of our proofs yield linear-time algorithms that produce the desired colorings.
LA - eng
KW - list coloring; edge coloring; total coloring; Vizing's Conjecture; Vizing's conjecture
UR - http://eudml.org/doc/270180
ER -

References

top
  1. [1] M. Behzad, Graphs and their chromatic numbers (Ph.D. thesis, Michigan State University, 1965). 
  2. [2] B. Bollabás and A.J. Harris, List-colorings of graphs, Graphs Combin. 1 (1985) 115-127, doi: 10.1007/BF02582936. 
  3. [3] O.V. Borodin, Generalization of a theorem of Kotzig and a prescribed coloring of the edges of planar graphs, Mathematical Notes of the Academy of Sciences of the USSR 48 (1990) 1186-1190, doi: 10.1007/BF01240258. Zbl0742.05039
  4. [4] 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
  5. [5] O.V. Borodin, Structural properties of plane graphs without adjacent triangles and an application to 3-colorings, J. Graph Theory 21 (1996) 183-186, doi: 10.1002/(SICI)1097-0118(199602)21:2<183::AID-JGT7>3.0.CO;2-N Zbl0838.05039
  6. [6] O.V. Borodin, A.V. Kostochka and D.R. Woodall, List edge and list total colourings of multigraphs, J. Comb. Theory (B) 71 (1997) 184-204, doi: 10.1006/jctb.1997.1780. Zbl0876.05032
  7. [7] P. Erdös, A.L. Rubin and H. Taylor, Choosability in graphs, Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Arcata, California, 1979), Congressus Numeratium 26 (1980) 125-157. 
  8. [8] R.P. Gupta, The chromatic index and the degree of a graph (Abstract 66T-429), Notices Amer. Math. Soc. 13 (1966) 719. 
  9. [9] T.R. Jensen and B. Toft, Graph Coloring Problems (John Wiley & Sons, 1995). 
  10. [10] M. Juvan, B. Mohar and R. Skrekovski, Graphs of degree 4 are 5-edge-choosable, J. Graph Theory, 32 (1999) 250-264, doi: 10.1002/(SICI)1097-0118(199911)32:3<250::AID-JGT5>3.0.CO;2-R Zbl0934.05052
  11. [11] A.V. Kostochka, List edge chromatic number of graphs with large girth, Discrete Math. 101 (1992) 189-201, doi: 10.1016/0012-365X(92)90602-C. Zbl0766.05027
  12. [12] A.V. Kostochka, The total coloring of a multigraph with maximal degree 4, Discrete Math. 17 (1977) 161-163, doi: 10.1016/0012-365X(77)90146-7. Zbl0411.05038
  13. [13] A.V. Kostochka, The total chromatic number of a multigraph with maximal degree 5 is at most 7, Discrete Math. 162 (1996) 199-214, doi: 10.1016/0012-365X(95)00286-6. Zbl0871.05023
  14. [14] A.V. Kostochka, Exact upper bound for the total chromatic number of a graph, Proc. 24th International Wiss. Koll., Tech. Hochsch. Ilmenau, (1979) 33-36 (in Russian). 
  15. [15] M. Rosenfeld, On the total coloring of certain graphs, Israel J. Math. 9 (1971) 396-402, doi: 10.1007/BF02771690. Zbl0211.56604
  16. [16] N. Vijayaditya, On total chromatic number of a graph, J. London Math. Soc. 3 (1971) 405-408, doi: 10.1112/jlms/s2-3.3.405. Zbl0223.05103
  17. [17] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964) 25-30 (in Russian). 
  18. [18] V.G. Vizing, Coloring the vertices of a graph in prescribed colors, Diskret. Analiz., No. 29 Metody Diskret. Anal. v Teorii Kodov i Shem (1976), 3-10, 101 (in Russian). 
  19. [19] V.G. Vizing, Critical graphs with a given chromatic class., Diskret. Analiz. 5 (1965) 9-17 (in Russian). 
  20. [20] W. Wang and K. Lih, Choosability and edge choosability of planar graphs without intersecting triangles, SIAM J. Discrete Math. 15 (2002) 538-545, doi: 10.1137/S0895480100376253. Zbl1006.05024
  21. [21] H.P. Yap, Total-colourings of graphs, Manuscript, 1989. Zbl0636.05025
  22. [22] L. Zhang and B. Wu, Edge choosability of planar graphs without small cycles, Discrete Math. 283 (2004) 289-293, doi: 10.1016/j.disc.2004.01.001. Zbl1042.05033

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.