Path graphs are intersection graphs of paths in a tree. We start from the characterization of path graphs by Monma and Wei (1986) [14] and we reduce it to some 2-coloring 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.
Two new characterizations of path graphs / Apollonio, Nicola; Balzotti, Lorenzo. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - 346:12(2023), p. 113596. [10.1016/j.disc.2023.113596]
Two new characterizations of path graphs
Lorenzo Balzotti
2023
Abstract
Path graphs are intersection graphs of paths in a tree. We start from the characterization of path graphs by Monma and Wei (1986) [14] and we reduce it to some 2-coloring 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.File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
