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), pp. 1-15. [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 | Dimensione | Formato | |
|---|---|---|---|
|
Apollonio_Two_2023.pdf
accesso aperto
Note: https://doi.org/10.1016/j.disc.2023.113596
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Creative commons
Dimensione
559.98 kB
Formato
Adobe PDF
|
559.98 kB | Adobe PDF |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
