Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: List edge-colorings of series-parallel graphs. | List edge-colorings of series-parallel graphs Martin Juvan Department of Mathematics University of Ljubljana 1111 Ljubljana Slovenia Bojan Mohar Department of Mathematics University of Ljubljana 1111 Ljubljana Slovenia Robin Thomasy School of Mathematics Georgia Institute of Technology Atlanta GA 30332 thomas@ Abstract It is proved that for every integer k 3 for every simple series-parallel graph G with maximum degree at most k and for every collection L e e 2 E G of sets each of size at least k there exists a proper edge-coloring of G such that for every edge e 2 E G the color of e belongs to L e . Submitted February 25 1999 Accepted September 17 1999. Mathematical Subject Classification 05C15. 1 Introduction List colorings are a generalization of usual colorings that recently attracted considerable attention cf. 1 8 9 11 . Originally list colorings were introduced by Vizing 12 Supported in part by the Ministry of Science and Technology of Slovenia Research Project J1-0502-0101-98. Part of the work was done while the author was visiting Georgia Institute of Technology. yPartially supported by NSF under Grant No. DMS-9623031 and by NSA under Grant No. MDA904-98-1-0517. 1 THE ELECTRONIC .JOURNAL OF COmBINATORICS 6 1999 R42 2 and Erdos Rubin and Taylor 6 in the seventies. The dehnition of a list edge-coloring is as follows. Let G be a multigraph. An edge-list assignment L E G P N is a function that assigns to each edge e of G a set or a list L e of admissible colors. A function A E G N is an L-edge-coloring if A e 2 L e for every e 2 E G and A e A f for every pair of adjacent edges e f 2 E G . A graph G is k-edge-choosable if it has an L-edge-coloring for every edge-list assignment L such that L e k for each e 2 E G . Our work is motivated by the following conjecture which apparently hrst appeared in 3 but was considered by many other researchers see 8 Problem . Conjecture Every graph G is .
