ON THE PATHWIDTH OF CHORDAL GRAPHS

In this paper we first show that the pathwidth problem for chordal gra phs is NP-hard. Then we give polynomial algorithms for subclasses. One of those classes are the k-starlike graphs -a generalization of split graphs. The other class are the primitive starlike graphs - a class o f graphs where the intersection behavior of maximal cliques is strongl y restricted.