Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Inforamtion Science and Engineering, Vol.18 No.3, pp.467-473 (May 2002)

Triangle Graphs and Simple Trapezoid Graphs

Yaw-Ling Lin
Department of Computer Science and Information Management
Providence University
Taichung, 433 Taiwan
E-mail: yllin@pu.edu.tw

In this paper, we present results on two subclasses of trapezoid graphs, including simple trapezoid graphs and triangle graphs (also known as PI graph in [3]). Simple trapezoid graphs and triangle graphs are proper subclasses of trapezoid graphs [3, 5]. Here we show that simple trapezoid graphs and triangle graphs are also two distinct subclasses of trapezoid graphs.

Keywords: triangle graphs, simple trapezoid graphs, parallelogram graphs, maximum clique, vertex coloring, maximum independent set, clique partition

Full Text () Retrieve PDF document (200205_10.pdf)

Received February 1, 2000; revised November 30, 2000; accepted April 25, 2001.
Communicated by Jeremy P. Spinrad.