IEICE Trans - Graph Coloring Algorithms

Graph Coloring Algorithms

Xiao ZHOU  Takao NISHIZEKI

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E83-D    No.3    pp.407-417
Publication Date: 2000/03/25
Online ISSN:
DOI:
Print ISSN: 0916-8532
Type of Manuscript: INVITED SURVEY PAPER
Category: Graph Algorithms
Keyword:
algorithm,  edge-coloring,  f-coloring,  [g,f]-coloring,  total coloring,

Full Text: PDF>>

Summary:
Graph coloring is a fundamental problem, which often appears in various scheduling problems like the file transfer problem on computer networks. In this paper, we survey recent advances and results on the edge-coloring, the f-coloring, the [g,f]-coloring, and the total coloring problem for various classes of graphs such as bipartite graphs, series-parallel graphs, planar graphs, and graphs having fixed degeneracy, tree-width, genus, arboricity, unicyclic index or thickness. In particular, we review various upper bounds on the minimum numbers of colors required to color these classes of graphs, and present efficient sequential and parallel algorithms to find colorings of graphs with these numbers of colors.