A General Framework for Coloring Problems: Old Results, New Results, and Open Problems

Hajo Broersma

doi:10.1007/978-3-540-30540-8_7

A General Framework for Coloring Problems: Old Results, New Results, and Open Problems

Hajo Broersma

Discrete Mathematics and Mathematical Programming

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

7 Citations (Scopus)

3 Downloads (Pure)

Abstract

n this survey paper we present a general framework for coloring problems that was introduced in a joint paper which the author presented at WG2003. We show how a number of different types of coloring problems, most of which have been motivated from frequency assignment, fit into this framework. We give a survey of the existing results, mainly based on and strongly biased by joint work of the author with several different groups of coauthors, include some new results, and discuss several open problems for each of the variants.

Original language	English
Title of host publication	Combinatorial Geometry and Graph Theory
Subtitle of host publication	Indonesia-Japan Joint Conference, IJCCGGT 2003, Bandung, Indonesia, September 13-16, 2003, Revised Selected Papers
Editors	Jin Akiyama, Edy Tri Baskoro, Mikio Kano
Place of Publication	Berlin
Publisher	Springer
Pages	65-79
Number of pages	14
ISBN (Electronic)	978-3-540-30540-8
ISBN (Print)	978-3-540-24401-1
DOIs	https://doi.org/10.1007/978-3-540-30540-8_7
Publication status	Published - 2005
Event	Indonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory, IJCCGGT 2003 - Bandung, Indonesia Duration: 13 Sept 2003 → 16 Sept 2003

Publication series

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

Conference

Conference	Indonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory, IJCCGGT 2003
Abbreviated title	IJCCGGT
Country/Territory	Indonesia
City	Bandung
Period	13/09/03 → 16/09/03

Keywords

Graph coloring
Graph partitioning
Forbidden subgraph
Planar graph
Computational complexity

Access to Document

10.1007/978-3-540-30540-8_7

7 Citations
1 Report

A general framework for coloring problems: old results, new results, and open problems
Broersma, H. J., 2003, Enschede: University of Twente. 14 p. (Memorandum; no. 1704)
Research output: Book/Report › Report › Other research output

Open Access
File

Cite this

Broersma, H. (2005). A General Framework for Coloring Problems: Old Results, New Results, and Open Problems. In J. Akiyama, E. T. Baskoro, & M. Kano (Eds.), Combinatorial Geometry and Graph Theory: Indonesia-Japan Joint Conference, IJCCGGT 2003, Bandung, Indonesia, September 13-16, 2003, Revised Selected Papers (pp. 65-79). (Lecture Notes in Computer Science; Vol. 3330). Springer. https://doi.org/10.1007/978-3-540-30540-8_7

Broersma, Hajo. / A General Framework for Coloring Problems : Old Results, New Results, and Open Problems. Combinatorial Geometry and Graph Theory: Indonesia-Japan Joint Conference, IJCCGGT 2003, Bandung, Indonesia, September 13-16, 2003, Revised Selected Papers. editor / Jin Akiyama ; Edy Tri Baskoro ; Mikio Kano. Berlin : Springer, 2005. pp. 65-79 (Lecture Notes in Computer Science).

@inproceedings{6b17351990d547d9bb467e94fd0e6f24,

title = "A General Framework for Coloring Problems: Old Results, New Results, and Open Problems",

abstract = "n this survey paper we present a general framework for coloring problems that was introduced in a joint paper which the author presented at WG2003. We show how a number of different types of coloring problems, most of which have been motivated from frequency assignment, fit into this framework. We give a survey of the existing results, mainly based on and strongly biased by joint work of the author with several different groups of coauthors, include some new results, and discuss several open problems for each of the variants.",

keywords = "Graph coloring, Graph partitioning , Forbidden subgraph, Planar graph, Computational complexity",

author = "Hajo Broersma",

year = "2005",

doi = "10.1007/978-3-540-30540-8\_7",

language = "English",

isbn = "978-3-540-24401-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "65--79",

editor = "Jin Akiyama and Baskoro, \{Edy Tri\} and Mikio Kano",

booktitle = "Combinatorial Geometry and Graph Theory",

address = "Germany",

note = "Indonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory, IJCCGGT 2003, IJCCGGT ; Conference date: 13-09-2003 Through 16-09-2003",

}

Broersma, H 2005, A General Framework for Coloring Problems: Old Results, New Results, and Open Problems. in J Akiyama, ET Baskoro & M Kano (eds), Combinatorial Geometry and Graph Theory: Indonesia-Japan Joint Conference, IJCCGGT 2003, Bandung, Indonesia, September 13-16, 2003, Revised Selected Papers. Lecture Notes in Computer Science, vol. 3330, Springer, Berlin, pp. 65-79, Indonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory, IJCCGGT 2003, Bandung, Indonesia, 13/09/03. https://doi.org/10.1007/978-3-540-30540-8_7

A General Framework for Coloring Problems: Old Results, New Results, and Open Problems. / Broersma, Hajo.
Combinatorial Geometry and Graph Theory: Indonesia-Japan Joint Conference, IJCCGGT 2003, Bandung, Indonesia, September 13-16, 2003, Revised Selected Papers. ed. / Jin Akiyama; Edy Tri Baskoro; Mikio Kano. Berlin: Springer, 2005. p. 65-79 (Lecture Notes in Computer Science; Vol. 3330).

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

TY - GEN

T1 - A General Framework for Coloring Problems

T2 - Indonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory, IJCCGGT 2003

AU - Broersma, Hajo

PY - 2005

Y1 - 2005

N2 - n this survey paper we present a general framework for coloring problems that was introduced in a joint paper which the author presented at WG2003. We show how a number of different types of coloring problems, most of which have been motivated from frequency assignment, fit into this framework. We give a survey of the existing results, mainly based on and strongly biased by joint work of the author with several different groups of coauthors, include some new results, and discuss several open problems for each of the variants.

AB - n this survey paper we present a general framework for coloring problems that was introduced in a joint paper which the author presented at WG2003. We show how a number of different types of coloring problems, most of which have been motivated from frequency assignment, fit into this framework. We give a survey of the existing results, mainly based on and strongly biased by joint work of the author with several different groups of coauthors, include some new results, and discuss several open problems for each of the variants.

KW - Graph coloring

KW - Graph partitioning

KW - Forbidden subgraph

KW - Planar graph

KW - Computational complexity

U2 - 10.1007/978-3-540-30540-8_7

DO - 10.1007/978-3-540-30540-8_7

M3 - Conference contribution

SN - 978-3-540-24401-1

T3 - Lecture Notes in Computer Science

SP - 65

EP - 79

BT - Combinatorial Geometry and Graph Theory

A2 - Akiyama, Jin

A2 - Baskoro, Edy Tri

A2 - Kano, Mikio

PB - Springer

CY - Berlin

Y2 - 13 September 2003 through 16 September 2003

ER -

Broersma H. A General Framework for Coloring Problems: Old Results, New Results, and Open Problems. In Akiyama J, Baskoro ET, Kano M, editors, Combinatorial Geometry and Graph Theory: Indonesia-Japan Joint Conference, IJCCGGT 2003, Bandung, Indonesia, September 13-16, 2003, Revised Selected Papers. Berlin: Springer. 2005. p. 65-79. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-30540-8_7

A General Framework for Coloring Problems: Old Results, New Results, and Open Problems

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Research output

A general framework for coloring problems: old results, new results, and open problems

Cite this