𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the structure of graphs with few P4s

✍ Scribed by Luitpold Babel; Stephan Olariu

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
984 KB
Volume
84
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

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, fi-reducible graphs, and &-sparse graphs.

πŸ“œ SIMILAR VOLUMES

SIMPLE MAX-CUT for unit interval graphs
SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s
✍ Hans L. Bodlaender; Ton Kloks; Rolf Niedermeier πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 56 KB

The SIMPLE MAX-CUT problem can be solved in linear time for unit interval graphs. We show also that for each constant q, the SIMPLE MAX-CUT problem can be solved in polynomial time for (q, q -4)-graphs.

On the embedding of graphs into graphs w
On the embedding of graphs into graphs with few eigenvalues
✍ Vu, Van H. πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 726 KB

A graph is called of type k if it is connected, regular, and has k distinct eigenvalues. For example graphs of type 2 are the complete graphs, while those of type 3 are the strongly regular graphs. We prove that for any positive integer n, every graph can be embedded in n cospectral, non-isomorphic