ON A UNIQUE TREE-REPRESENTATION FOR P4-EXTENDIBLE GRAPHS

Several practical applications in computer science and computational linguistics suggest the study of graphs that are unlikely to have more than a few induced paths of length three. These applications have motivated the notion of a cograph, defined by the very strong restriction that no vertex may belong to an induced path of length three. The class of P4-extendible graphs that we introduce in this paper relaxes this restriction, and in fact properly contains the class of cographs, while still featuring the remarkable property of admitting a unique tree representation. Just as in the case of cographs, the class of P4-extendible graphs finds applications to clustering, scheduling, and memory management in a computer system. We give several characterizations for P4-extendible graphs and show that they can be constructed from single-vertex graphs by a finite sequence of operations. Our characterization implies that the P4-extendible graphs admit a tree representation unique up to isomorphism. Furthermore, this tree representation can be obtained in polynomial time.