Infinite Family from Each Vertex k-Critical Graph without Any Critical Edge

摘要

In 1970, Dirac conjectured that for each integer k ≥ 4, there exists a vertex k-critical graph without any critical edge. In this paper, we introduce strict-vertex critically (k - l)-de-chromatic pair, strict 2-vertex decomposition graph and so on. By studying their relevant properties, we obtain that any vertex k-critical graph without any critical edge generates an infinite family of vertex k-critical graphs without critical edges.