We first present new structural properties of a two-pair in various graphs. A two-pair is used for characterizing weakly chordal graphs. Based on these properties, we prove the main theorem: a graph G is a weakly chordal (K 2,3 , P 6 , 4P 2 , P 2  U P 4 , Hi, H 2 , H 3 )-free graph if and only if G is an edge intersection graph of subtrees on a tree with maximum degree 4. This characterizes the so called [4,4, 2] graphs. The proof of the theorem constructively finds the representation. Thus, we obtain a algorithm to construct an edge intersection model of subtrees on a tree with maximum degree 4 for such a given graph. This is a recognition algorithm for [4, 4, 2] graphs.
['Martin Charles Golumbic', 'Marina Lipshteyn', 'Michal Stern']
Finding intersection models of weakly chordal graphs