ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2019: 0.600
Rejection Rate (2018-2019): c. 84%
Discussiones Mathematicae Graph Theory 29(1) (2009)
Daniel W. Cranston
University of Illinois, Urbana, USA
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
Keywords: list coloring, edge coloring, total coloring,
2000 Mathematics Subject Classification: 05C15, 05C10.
Received 18 January 2008
Revised 20 October 2008
Accepted 20 October 2008