Complexity of coloring graphs without forbidden subgraphs

Daniel Král; Jan Kratochvil; Zsolt Tuza; Gerhard Woeginger

doi:10.1007/3-540-45477-2_23

Complexity of coloring graphs without forbidden subgraphs

Daniel Král, Jan Kratochvil, Zsolt Tuza, Gerhard Woeginger

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

154 Citations (Scopus)

21 Downloads (Pure)

Abstract

We give a complete characterization of parameter graphs H for which the problem of coloring H-free graphs is polynomial and for which it is NP-complete. We further initiate a study of this problem for two forbidden subgraphs.

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science
Subtitle of host publication	27th InternationalWorkshop, WG 2001 Boltenhagen, Germany, June 14–16, 2001 Proceedings
Editors	Andreas Brandstädt, Van Bang Le
Place of Publication	Berlin
Publisher	Springer
Pages	254-262
ISBN (Electronic)	978-3-540-45477-9
ISBN (Print)	978-3-540-42707-0
DOIs	https://doi.org/10.1007/3-540-45477-2_23
Publication status	Published - 2001
Event	27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2001 - Boltenhagen, Germany Duration: 14 Jun 2001 → 16 Jun 2001 Conference number: 27

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2204
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2001
Abbreviated title	WG
Country/Territory	Germany
City	Boltenhagen
Period	14/06/01 → 16/06/01

Keywords

METIS-203194

Access to Document

10.1007/3-540-45477-2_23

Cite this

Král, D., Kratochvil, J., Tuza, Z., & Woeginger, G. (2001). Complexity of coloring graphs without forbidden subgraphs. In A. Brandstädt, & V. B. Le (Eds.), Graph-Theoretic Concepts in Computer Science: 27th InternationalWorkshop, WG 2001 Boltenhagen, Germany, June 14–16, 2001 Proceedings (pp. 254-262). (Lecture Notes in Computer Science; Vol. 2204). Springer. https://doi.org/10.1007/3-540-45477-2_23

@inproceedings{e2c8d14163464084b8fc1b4087f51f89,

title = "Complexity of coloring graphs without forbidden subgraphs",

abstract = "We give a complete characterization of parameter graphs H for which the problem of coloring H-free graphs is polynomial and for which it is NP-complete. We further initiate a study of this problem for two forbidden subgraphs.",

keywords = "METIS-203194",

author = "Daniel Kr{\'a}l and Jan Kratochvil and Zsolt Tuza and Gerhard Woeginger",

year = "2001",

doi = "10.1007/3-540-45477-2_23",

language = "English",

isbn = "978-3-540-42707-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "254--262",

editor = "Andreas Brandst{\"a}dt and Le, {Van Bang}",

booktitle = "Graph-Theoretic Concepts in Computer Science",

address = "Germany",

note = "27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2001, WG ; Conference date: 14-06-2001 Through 16-06-2001",

}

Král, D, Kratochvil, J, Tuza, Z & Woeginger, G 2001, Complexity of coloring graphs without forbidden subgraphs. in A Brandstädt & VB Le (eds), Graph-Theoretic Concepts in Computer Science: 27th InternationalWorkshop, WG 2001 Boltenhagen, Germany, June 14–16, 2001 Proceedings. Lecture Notes in Computer Science, vol. 2204, Springer, Berlin, pp. 254-262, 27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2001, Boltenhagen, Germany, 14/06/01. https://doi.org/10.1007/3-540-45477-2_23

Complexity of coloring graphs without forbidden subgraphs. / Král, Daniel; Kratochvil, Jan; Tuza, Zsolt et al.
Graph-Theoretic Concepts in Computer Science: 27th InternationalWorkshop, WG 2001 Boltenhagen, Germany, June 14–16, 2001 Proceedings. ed. / Andreas Brandstädt; Van Bang Le. Berlin: Springer, 2001. p. 254-262 (Lecture Notes in Computer Science; Vol. 2204).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Complexity of coloring graphs without forbidden subgraphs

AU - Král, Daniel

AU - Kratochvil, Jan

AU - Tuza, Zsolt

AU - Woeginger, Gerhard

N1 - Conference code: 27

PY - 2001

Y1 - 2001

N2 - We give a complete characterization of parameter graphs H for which the problem of coloring H-free graphs is polynomial and for which it is NP-complete. We further initiate a study of this problem for two forbidden subgraphs.

AB - We give a complete characterization of parameter graphs H for which the problem of coloring H-free graphs is polynomial and for which it is NP-complete. We further initiate a study of this problem for two forbidden subgraphs.

KW - METIS-203194

U2 - 10.1007/3-540-45477-2_23

DO - 10.1007/3-540-45477-2_23

M3 - Conference contribution

SN - 978-3-540-42707-0

T3 - Lecture Notes in Computer Science

SP - 254

EP - 262

BT - Graph-Theoretic Concepts in Computer Science

A2 - Brandstädt, Andreas

A2 - Le, Van Bang

PB - Springer

CY - Berlin

T2 - 27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2001

Y2 - 14 June 2001 through 16 June 2001

ER -

Král D, Kratochvil J, Tuza Z, Woeginger G. Complexity of coloring graphs without forbidden subgraphs. In Brandstädt A, Le VB, editors, Graph-Theoretic Concepts in Computer Science: 27th InternationalWorkshop, WG 2001 Boltenhagen, Germany, June 14–16, 2001 Proceedings. Berlin: Springer. 2001. p. 254-262. (Lecture Notes in Computer Science). doi: 10.1007/3-540-45477-2_23

Complexity of coloring graphs without forbidden subgraphs

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this