From path graphs to directed path graphs

DOI10.1007/978-3-642-16926-7_24MaRDI QIDQ3057630zbMATH OpenOpenAlexFDO

Authors Steven Chaplick, M. Gutierrez, Benjamin Lévêque, Silvia B. Tondato

Publication date 16 November 2010

Published in Graph Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://hal-lirmm.ccsd.cnrs.fr/lirmm-00620726/file/From_Path_Graphs_to_Directed_Path_Graphs.pdf

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• On models of directed path graphs non rooted directed path graphs
• Recognizing clique graphs of directed edge path graphs
• Two new characterizations of path graphs
• A faster algorithm to recognize undirected path graphs
• Recognizing \(k\)-path graphs

Cites work

• A faster algorithm to recognize undirected path graphs
• A recognition algorithm for the intersection graphs of paths in trees
• Algorithmic graph theory and perfect graphs
• Characterizing path graphs by forbidden induced subgraphs
• Incidence matrices and interval graphs
• Intersection graphs of paths in a tree
• The forbidden subgraph characterization of directed vertex graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Topics in Intersection Graph Theory

Cited in

(9)

• On models of directed path graphs non rooted directed path graphs
• Isomorphisms and traversability of directed path graphs
• scientific article; zbMATH DE number 3893233 (Why is no real title available?)
• scientific article; zbMATH DE number 5879503 (Why is no real title available?)
• scientific article; zbMATH DE number 4183442 (Why is no real title available?)
• Intersection graphs of non-crossing paths
• Two new characterizations of path graphs
• Simpler and unified recognition algorithm for path graphs and directed path graphs
• Asteroidal quadruples in non rooted path graphs

This page was built for publication: From path graphs to directed path graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3057630)