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
Nicola ApollonioCo-primo
;
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 in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
1-s2.0-S0012365X23002820-main_print.pdf
accesso aperto
Tipologia:
Versione Editoriale (PDF)
Licenza:
Altro tipo di licenza
Dimensione
560.09 kB
Formato
Adobe PDF
|
560.09 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
