Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0658.05067
Dagan, Ido; Golumbic, Martin Charles; Pinter, Ron Yair
Trapezoid graphs and their coloring. (English)
[J] Discrete Appl. Math. 21, No.1, 35-46 (1988). ISSN 0166-218X

The authors' abstract: ``We define trapezoid graphs, an extension of both interval and permutation graphs. We show that this new class properly contains the union of the two classes, and that trapezoid graphs are equivalent to the incomparability graphs of partially ordered sets having interval order dimension at most two. We provide an optimal coloring algorithm for trapezoid graphs that runs in time O(nk), where n is the number of nodes and k is the chromatic number of the graph. Our coloring algorithm has direct applications to channel routing on integrated circuits.''
[R.L.Hemminger]

MSC 2000:: *05C99 Graph theory
05C15 Chromatic theory of graphs and maps

Keywords: interval graphs; trapezoid graphs; permutation graphs; incomparability graphs; coloring algorithm; channel routing

Cited in: Zbl 0749.05052 Zbl 0728.06003

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]