Intersection graphs of vertex disjoint paths in a tree.

*(English)*Zbl 0837.05094The paper characterizes the intersection graphs of internally vertex disjoint path in a tree in terms of maximal clique separators and by forbidden subgraphs and presents an algorithm recognizing these graphs in time \(O(n^4m)\).

Reviewer: H.Müller (Jena)

##### MSC:

05C75 | Structural characterization of families of graphs |

05C85 | Graph algorithms (graph-theoretic aspects) |

05C05 | Trees |

05C38 | Paths and cycles |

68R10 | Graph theory (including graph drawing) in computer science |

PDF
BibTeX
XML
Cite

\textit{B. S. Panda} and \textit{S. P. Mohanty}, Discrete Math. 146, No. 1--3, 179--209 (1995; Zbl 0837.05094)

Full Text:
DOI

##### References:

[1] | Buneman, P., A characterization of rigid circuit graphs, Discrete math., 9, 205-212, (1974) · Zbl 0288.05128 |

[2] | Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs, J. combin. theory ser. B, 16, 47-56, (1974) · Zbl 0266.05101 |

[3] | Gavril, F., A recognition algorithm for the intersection graphs of directed paths in directed trees, Discrete math., 13, 237-249, (1975) · Zbl 0312.05108 |

[4] | Gavril, F., A recognition algorithm for the intersection graphs of paths in trees, Discrete math., 23, 211-227, (1978) · Zbl 0398.05060 |

[5] | Golumbic, M.C.; Jamison, R.E., The edge intersection graphs of paths in a tree, J. combin. theory ser. B, 38, 8-22, (1985) · Zbl 0537.05063 |

[6] | Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic press New York · Zbl 0541.05054 |

[7] | Klee, V., What are the intersection graphs of arcs in a circle?, Amer. math. monthly, 76, 810-813, (1969) |

[8] | W.A. Lobb, Perfect graphs from paths in trees, unpublished manuscript. · Zbl 1200.57011 |

[9] | Monma, C.L.; Wei, V.K., Intersection graphs of paths in a tree, J. combin. theory ser. B, 41, 141-181, (1986) · Zbl 0595.05062 |

[10] | Renz, P.L., Intersection representation of graphs by arcs, Pacific J. math., 34, 501-510, (1970) · Zbl 0191.55103 |

[11] | F.S. Roberts, Discrete Mathematical Model with Applications to Social, Biological and Environmental Problems (Prentice-Hall, Englewood cliffs, NJ). · Zbl 0363.90002 |

[12] | Samy, A.N.; Arumugam, G.; Paul Devasahayam, M.; Xavier, C., A recognition algorithm for the intersection graphs of internally disjoint paths in trees, (), 169-178 |

[13] | Syslo, M.M, Triangulated edge intersection graphs of paths in a tree, Discrete math., 55, 217-220, (1985) · Zbl 0569.05045 |

[14] | Tarjan, R.E., Decomposition by clique separators, Discrete math., 55, 221-231, (1985) · Zbl 0572.05039 |

[15] | Walter, J.R., Representations of chordal graphs as subtrees of a tree, J. graph theory, 2, 265-267, (1978) · Zbl 0441.05022 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.