On the structure of graphs with few \(P_4\)s (Q1392556)

This paper deals with the \(P_4\) structure of graphs (\(P_4\) denotes a path of length 3). A \((q,t)\) graph is one in which no set of \(q\) or fewer vertices induces more than \(t\) distinct \(P_4\)'s. The main result of this paper is that \((q,q-4)\) graphs form a class of graphs for which the isomorphism problem can be solved in polynomial time. The authors show that \((q,q-4)\) graphs can be encoded as rooted trees whose internal nodes represent certain graph operations and whose leaves correspond to certain basic graphs. As a result of this tree encoding isomorphism tests between \((q,q-4)\) graphs can be done in polynomial time. Another interesting result proved is that all \((q,q-4)\) graphs with \(4\leq q\leq 8\) are brittle. A graph \(G\) is brittle if each induced subgraph \(H\) of \(G\) contains a vertex which is either not the endpoint or not the midpoint of any \(P_4\) in \(H\). The graphs in this class are distinct from all previously known brittle graphs.