JISE Vol.18 No.3 #10

[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

Retrieve PDF document (200205_10.pdf)

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