Two new characterizations of path graphs

DOI10.1016/J.DISC.2023.113596MaRDI QIDQ6056699zbMATH OpenOpenAlexFDO

Authors Nicola Apollonio, Lorenzo Balzotti

Publication date 4 October 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2208.01001

zbMATH Keywords

clique path treeminimal forbidden subgraphspath graphs

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38)

Abstract: Path graphs are intersection graphs of paths in a tree. We start from the characterization of path graphs by Monma and Wei [C.L.~Monma,~and~V.K.~Wei, Intersection Graphs of Paths in a Tree, J. Combin. Theory Ser. B, 41:2 (1986) 141--181] and we reduce it to some 2-colorings subproblems, obtaining the first characterization that directly leads to a polynomial recognition algorithm. Then we introduce the collection of the attachedness graphs of a graph and we exhibit a list of minimal forbidden 2-edge colored subgraphs in each of the attachedness graph.

Recommendations

• Characterizing path graphs by forbidden induced subgraphs
• scientific article; zbMATH DE number 3912430
• Intersection graphs of short paths in a tree
• Recognizing \(k\)-path graphs
• A faster algorithm to recognize undirected path graphs

Cites work

• A faster algorithm to recognize undirected path graphs
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• A recognition algorithm for the intersection graphs of paths in trees
• Asteroidal quadruples in non rooted path graphs
• Asteroids in rooted and directed path graphs
• Characterizing directed path graphs by forbidden asteroids
• Characterizing path graphs by forbidden induced subgraphs
• Decomposition by clique separators
• From path graphs to directed path graphs
• Intersection graphs of paths in a tree
• Intersection representations of graphs by arcs
• On models of directed path graphs non rooted directed path graphs
• Representation of a finite graph by a set of intervals on the real line
• The forbidden subgraph characterization of directed vertex graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs

Cited in

(8)

• Intersection graphs of vertex disjoint paths in a tree
• Recognizing \(k\)-path graphs
• New results on path-decompositions and their down-links
• From path graphs to directed path graphs
• Characterizing path graphs by forbidden induced subgraphs
• scientific article; zbMATH DE number 16016 (Why is no real title available?)
• scientific article; zbMATH DE number 7103402 (Why is no real title available?)
• Simpler and unified recognition algorithm for path graphs and directed path graphs

This page was built for publication: Two new characterizations of path graphs

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