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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)

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 languageEnglish
Title of host publicationCombinatorial Geometry and Graph Theory
Subtitle of host publicationIndonesia-Japan Joint Conference, IJCCGGT 2003, Bandung, Indonesia, September 13-16, 2003, Revised Selected Papers
EditorsJin Akiyama, Edy Tri Baskoro, Mikio Kano
Place of PublicationBerlin
PublisherSpringer
Pages65-79
Number of pages14
ISBN (Electronic)978-3-540-30540-8
ISBN (Print)978-3-540-24401-1
DOIs
Publication statusPublished - 2005
EventIndonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory, IJCCGGT 2003 - Bandung, Indonesia
Duration: 13 Sep 200316 Sep 2003

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume3330
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceIndonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory, IJCCGGT 2003
Abbreviated titleIJCCGGT
CountryIndonesia
CityBandung
Period13/09/0316/09/03

Fingerprint

Colouring
Open Problems
Frequency Assignment
Biased
Framework

Keywords

  • METIS-226160
  • Graph coloring
  • Graph partitioning
  • Forbidden subgraph
  • Planar graph
  • Computational Complexity

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). Berlin: 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 = "METIS-226160, 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",

}

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 proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - A General Framework for Coloring Problems

T2 - Old Results, New Results, and Open Problems

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 - METIS-226160

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

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). https://doi.org/10.1007/978-3-540-30540-8_7