The Two-Coloring number and degenerate colorings of planar graphs

Henry Kierstead; Bojan Mohar; Simon Špacapan; Daqing Yang; Xuding Zhiu

doi:10.1137/070703697

The Two-Coloring number and degenerate colorings of planar graphs

Henry Kierstead, Bojan Mohar, Simon Špacapan, Daqing Yang, Xuding Zhiu

Research output: Contribution to journal › Article › peer-review

11 Scopus citations

Abstract

The two-coloring number of graphs, which was originally introduced in the study of the game chromatic number, also gives an upper bound on t he degenerate chromatic number as introduced by Borodin. It is proved that the two-coloring number of any planar graph is at most nine. As a consequence, the degenerate list chromatic number of any planar graph is at most nine. It is also shown that the degenerate diagonal chromatic number is at most 11 and the degenerate diagonal list chromatic number is at most 12 for all planar graphs.

Original language	English (US)
Pages (from-to)	1548-1560
Number of pages	13
Journal	SIAM Journal on Discrete Mathematics
Volume	23
Issue number	3
DOIs	https://doi.org/10.1137/070703697
State	Published - Dec 1 2009

Keywords

Degenerate coloring
Planar graph
Two-coloring number

ASJC Scopus subject areas

Mathematics(all)

Access to Document

10.1137/070703697

Cite this

@article{a80e1be153ac4b35a5f1e69c0b6b749a,

title = "The Two-Coloring number and degenerate colorings of planar graphs",

abstract = "The two-coloring number of graphs, which was originally introduced in the study of the game chromatic number, also gives an upper bound on t he degenerate chromatic number as introduced by Borodin. It is proved that the two-coloring number of any planar graph is at most nine. As a consequence, the degenerate list chromatic number of any planar graph is at most nine. It is also shown that the degenerate diagonal chromatic number is at most 11 and the degenerate diagonal list chromatic number is at most 12 for all planar graphs.",

keywords = "Degenerate coloring, Planar graph, Two-coloring number",

author = "Henry Kierstead and Bojan Mohar and Simon {\v S}pacapan and Daqing Yang and Xuding Zhiu",

year = "2009",

month = dec,

day = "1",

doi = "10.1137/070703697",

language = "English (US)",

volume = "23",

pages = "1548--1560",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - The Two-Coloring number and degenerate colorings of planar graphs

AU - Kierstead, Henry

AU - Mohar, Bojan

AU - Špacapan, Simon

AU - Yang, Daqing

AU - Zhiu, Xuding

PY - 2009/12/1

Y1 - 2009/12/1

N2 - The two-coloring number of graphs, which was originally introduced in the study of the game chromatic number, also gives an upper bound on t he degenerate chromatic number as introduced by Borodin. It is proved that the two-coloring number of any planar graph is at most nine. As a consequence, the degenerate list chromatic number of any planar graph is at most nine. It is also shown that the degenerate diagonal chromatic number is at most 11 and the degenerate diagonal list chromatic number is at most 12 for all planar graphs.

AB - The two-coloring number of graphs, which was originally introduced in the study of the game chromatic number, also gives an upper bound on t he degenerate chromatic number as introduced by Borodin. It is proved that the two-coloring number of any planar graph is at most nine. As a consequence, the degenerate list chromatic number of any planar graph is at most nine. It is also shown that the degenerate diagonal chromatic number is at most 11 and the degenerate diagonal list chromatic number is at most 12 for all planar graphs.

KW - Degenerate coloring

KW - Planar graph

KW - Two-coloring number

UR - http://www.scopus.com/inward/record.url?scp=73249150067&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=73249150067&partnerID=8YFLogxK

U2 - 10.1137/070703697

DO - 10.1137/070703697

M3 - Article

AN - SCOPUS:73249150067

SN - 0895-4801

VL - 23

SP - 1548

EP - 1560

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 3

ER -

The Two-Coloring number and degenerate colorings of planar graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this