A P4 is a set of four vertices of a graph that induces a chordless path; the P4-structure of a graph is the set of all P4's. Vasek Chvatal asked if there is a polynomial time algorithm to determine whether an arbitrary four-uniform hypergraph is the P4-structure of some graph. The answer is yes; we present such an algorithm.
展开▼
机译： P 4 是图形的四个顶点的集合，该四个顶点诱发无弦路径;图的 P 4 结构是所有 P 4 的集合。 Vasek Chvatal询问是否存在多项式时间算法来确定任意四均匀超图是否是某些图的 P 4 结构。答案是肯定的。我们提出了这样的算法。
展开▼
