Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Computer Sciences
On The Structure Of Graphs With Few P4s, Luitpold Babel, Stephan Olariu
On The Structure Of Graphs With Few P4s, Luitpold Babel, Stephan Olariu
Computer Science Faculty Publications
We present new classes of graphs for which the isomorphism problem can be solved in polynomial time. These graphs are characterized by containing — in some local sense — only a small number of induced paths of length three. As it turns out, every such graph has a unique tree representation: the internal nodes correspond to three types of graph operations, while the leaves are basic graphs with a simple structure. The paper extends and generalizes known results about cographs, P4-reducible graphs, and P4-sparse graphs.