Journal Article
@Article
Artikel in Fachzeitschrift
Show entries of:
this year
(2021) |
last year
(2020) |
two years ago
(2019) |
Notes URL
Action:
login to update
Options:
Goto entry point
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
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