JISE

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

Journal of Information Science and Engineering, Vol. 18 No. 3, pp. 467-473

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 (JISE_200203_10.pdf)