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.
翻译：路径图是树中路径的交叉图。 我们从Monma和Wei[C.L.~Monma,~和~V.K.~wei,树中路径的交叉图, J. 组合。 Theory Ser. B, 41: 2(1986) 141- 181]对路径图的定性开始, 我们将其缩小为两个颜色的子问题, 获得第一个直接导致多元识别算法的特征图。 然后我们介绍一个图的附着性图的集合, 我们在每个附图中展示一个最少禁止的两端彩色子图的清单 。
相关内容
微信扫码咨询专知VIP会员