No label defined (Q3689221)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3912430
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3912430

      Statements

      0 references
      0 references
      1986
      0 references
      chordal graphs
      0 references
      intersection graph
      0 references
      paths in a tree
      0 references
      perfect graphs
      0 references
      The intersection graph for a family of sets is obtained by associating each set with a vertex of the graph and joining two vertices by an edge exactly when their corresponding sets have a nonempty intersection. Intersection graphs arise naturally in many contexts, such as scheduling conflicting events, and have been widely studied. We present a unified framework for studying several classes of intersection graphs arising from families of paths in a tree. Four distinct classes of graphs arise by considering paths to be the sets of vertices or the sets of edges making up the path, and by allowing by underlying tree to be undirected or directed; in the latter case only directed paths are allowed. Two further classes are obtained by requiring the directed tree to be rooted. We introduce other classes of graphs as well. The rooted directed vertex path graphs have been studied by Gavril; the vertex path graphs have been studied by Gavril and Renz; the edge path graphs have been studied by Golumbic and Jamison, Lobb, Syslo, and Tarjan. The main results are a characterization of these graphs in terms of their ''clique tree'' representations and a unified recognition algorithm. The algorithm repeatedly separates an arbitrary graph by a (maximal) clique separator, checks the form of the resultant nondecomposable ''atoms'', and finally checks that each separation step is valid. In all cases, the first two steps can be performed in polynomial time. In all but one case, the final step is based on a certain two-coloring condition and so can be done efficiently; in the other case the recognition problem can be shown to be NP-complete since a certain three-coloring condition is needed. The strength of this unified approach is that it clarifies and unifies virtually all of the important known results for these graphs and provides substantial new results as well. For example, the exact intersecting relationships among these graphs, and between these graphs and chordal and perfect graphs fall out easily as corollaries. A number of other results, such as bounds on the number of (maximal) cliques, related optimization problems on these graphs, etc., are presented along with open problems.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references