On coloring of sparse graphs

Alexandr Kostochka; Matthew Yancey

doi:10.1007/978-3-642-38536-0_20

On coloring of sparse graphs

Alexandr Kostochka, Matthew Yancey

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Graph coloring has numerous applications and is a well-known NP-complete problem. The goal of this paper is to survey recent results of the authors on coloring and improper coloring of sparse graphs and to point out some polynomial-time algorithms for coloring (not necessarily optimal) of graphs with bounded maximum average degree.

Original language	English (US)
Title of host publication	Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013
Publisher	Springer
Pages	224-234
Number of pages	11
ISBN (Print)	9783642385353
DOIs	https://doi.org/10.1007/978-3-642-38536-0_20
State	Published - 2013
Event	8th International Computer Science Symposium in Russia, CSR 2013 - Ekaterinburg, Russian Federation Duration: Jun 25 2013 → Jun 29 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7913 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	8th International Computer Science Symposium in Russia, CSR 2013
Country/Territory	Russian Federation
City	Ekaterinburg
Period	6/25/13 → 6/29/13

Keywords

graph coloring
improper coloring
k-critical graphs

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/978-3-642-38536-0_20

Library availability

Discover UIUC Full Text

Cite this

Kostochka, A., & Yancey, M. (2013). On coloring of sparse graphs. In Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013 (pp. 224-234). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7913 LNCS). Springer. https://doi.org/10.1007/978-3-642-38536-0_20

On coloring of sparse graphs. / Kostochka, Alexandr; Yancey, Matthew.
Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013. Springer, 2013. p. 224-234 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7913 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kostochka, A & Yancey, M 2013, On coloring of sparse graphs. in Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7913 LNCS, Springer, pp. 224-234, 8th International Computer Science Symposium in Russia, CSR 2013, Ekaterinburg, Russian Federation, 6/25/13. https://doi.org/10.1007/978-3-642-38536-0_20

@inproceedings{e09b5669d4a14bc288e5f3e3d6acf803,

title = "On coloring of sparse graphs",

abstract = "Graph coloring has numerous applications and is a well-known NP-complete problem. The goal of this paper is to survey recent results of the authors on coloring and improper coloring of sparse graphs and to point out some polynomial-time algorithms for coloring (not necessarily optimal) of graphs with bounded maximum average degree.",

keywords = "graph coloring, improper coloring, k-critical graphs",

author = "Alexandr Kostochka and Matthew Yancey",

year = "2013",

doi = "10.1007/978-3-642-38536-0_20",

language = "English (US)",

isbn = "9783642385353",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "224--234",

booktitle = "Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013",

address = "Germany",

}

TY - GEN

T1 - On coloring of sparse graphs

AU - Kostochka, Alexandr

AU - Yancey, Matthew

PY - 2013

Y1 - 2013

N2 - Graph coloring has numerous applications and is a well-known NP-complete problem. The goal of this paper is to survey recent results of the authors on coloring and improper coloring of sparse graphs and to point out some polynomial-time algorithms for coloring (not necessarily optimal) of graphs with bounded maximum average degree.

AB - Graph coloring has numerous applications and is a well-known NP-complete problem. The goal of this paper is to survey recent results of the authors on coloring and improper coloring of sparse graphs and to point out some polynomial-time algorithms for coloring (not necessarily optimal) of graphs with bounded maximum average degree.

KW - graph coloring

KW - improper coloring

KW - k-critical graphs

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

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

U2 - 10.1007/978-3-642-38536-0_20

DO - 10.1007/978-3-642-38536-0_20

M3 - Conference contribution

AN - SCOPUS:84888236941

SN - 9783642385353

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 224

EP - 234

BT - Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013

PB - Springer

T2 - 8th International Computer Science Symposium in Russia, CSR 2013

Y2 - 25 June 2013 through 29 June 2013

ER -

On coloring of sparse graphs

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this