Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2018) | last year (2017) | two years ago (2016) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Cole, Richard
Kowalik, Lukasz
Skrekovski, Riste

dblp
dblp
dblp

Not MPG Author(s):

Cole, Richard
Skrekovski, Riste

BibTeX cite key*:

KowalikKotzig

Title

Title*:

A Generalization of Kotzig's Theorem and Its Application

Journal

Journal Title*:

SIAM Journal on Discrete Mathematics

Journal's URL:

http://epubs.siam.org/

Download URL
for the article:

http://link.aip.org/link/?SJD/21/93/1

Language:

English

Publisher

Publisher's
Name:

SIAM

Publisher's URL:


Publisher's
Address:

Philadelphia, PA, USA

ISSN:

0895-4801

Vol, No, pp, Date

Volume*:

21

Number:

1

Publishing Date:

February 2007

Pages*:

93-106

Number of
VG Pages:


Page Start:

93

Page End:

106

Sequence Number:


DOI:

10.1137/050646196

Note, Abstract, ©

Note:


(LaTeX) Abstract:

An edge of a graph is light when the sum of the degrees of its end-vertices is at most 13. The well-known Kotzig theorem states that every 3-connected planar graph contains a light edge. Later, Borodin [J. Reine Angew. Math., 394 (1989), pp. 180–185] extended this result to the class of planar graphs of minimum degree at least 3. We deal with generalizations of these results for planar graphs of minimum degree 2. Borodin, Kostochka, and Woodall [J. Combin. Theory Ser. B, 71 (1997), pp. 184–204] showed that each such graph contains a light edge or a member of two infinite sets of configurations, called 2-alternating cycles and 3-alternators. This implies that planar graphs with maximum degree $\Delta \geq 12$ are $\Delta$-edge-choosable. We prove a similar result with 2-alternating cycles and 3-alternators replaced by five fixed bounded-sized configurations called crowns. This gives another proof of $\Delta$-edge-choosability of planar graphs with $\Delta \geq 12$. However, we show efficient choosability; i.e., we describe a linear-time algorithm for $\max\{\Delta,12\}$-edge-list-coloring planar graphs. This extends the result of Chrobak and Yung [J. Algorithms, 10 (1989), pp. 35–51].

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{KowalikKotzig,
AUTHOR = {Cole, Richard and Kowalik, Lukasz and Skrekovski, Riste},
TITLE = {A Generalization of {Kotzig's} Theorem and Its Application},
JOURNAL = {SIAM Journal on Discrete Mathematics},
PUBLISHER = {SIAM},
YEAR = {2007},
NUMBER = {1},
VOLUME = {21},
PAGES = {93--106},
ADDRESS = {Philadelphia, PA, USA},
MONTH = {February},
ISBN = {0895-4801},
DOI = {10.1137/050646196},
}


Entry last modified by Anja Becker, 02/28/2008
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Mathias Bader
Created
03/10/2007 09:05:49 AM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Anja Becker
Anja Becker
Lukasz Kowalik
Lukasz Kowalik
Lukasz Kowalik
Edit Dates
08.02.2008 13:52:09
08.02.2008 13:38:00
2007-03-13 16:04:09
2007-03-13 16:01:20
10.03.2007 09:05:49