On a new class of intersection graphs. (English) Zbl 0767.05079

Koebe, Manfred

Combinatorics, graphs and complexity, Proc. 4th Czech. Symp., Prachatice/ Czech. 1990, Ann. Discrete Math. 51, 141-143 (1992).

[For the entire collection see Zbl 0748.00023.]
In the present paper so-called spider graphs are investigated; these are finite undirected simple graphs, and they are a common generalization of interval, permutation, and circle graphs, therefore they belong to the class of intersection graphs. At first there are given some notions which are necessary to define spider graphs, and for instance they can be constructed — out of the already mentioned special graphs — from all trees, cycles, and trapezoid graphs. A first result is formulated by Theorem 1: Every chordal graph is a spider graph.
The class of spider graphs is characterized by forbidden substructures, and by the Theorems 2 and 3 a necessary and sufficient condition for graphs \(G\) to be spider graphs is given. The constructive proof of the sufficiency is sketched, and it can be used to get an efficient algorithm for spider graphs. In this context the author finds the result, that this recognition problem is polynomially solvable.
For details the author refers to his forthcoming paper “Spider graphs – - a new class of intersection graphs”.

Reviewer: H.-J.Presia (Ilmenau)

MSC:

05C75

Structural characterization of families of graphs

Keywords:

spider graphs; intersection graphs

Citations:

Zbl 0748.00023