Two new characterizations of path graphs

DOI10.1016/J.DISC.2023.113596zbMATH Open1522.05234arXiv2208.01001OpenAlexW4385222054MaRDI QIDQ6056699FDOQ6056699

Nicola Apollonio, Lorenzo Balzotti

Publication date: 4 October 2023

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

zbMATH Keywords

path graphsminimal forbidden subgraphsclique path tree

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

• Title not available (Why is that?)
• Title not available (Why is that?)
• New results on path-decompositions and their down-links

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)