On the structure of graphs with few P4s
✍
Luitpold Babel; Stephan Olariu
📂
Article
📅
1998
🏛
Elsevier Science
🌐
English
⚖ 984 KB
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 intern