Graphs with large maximum degree containing no edge-critical graphs

摘要

We say that a graph is edge-critical if it contains an edge whose deletion reduces its chromatic number. Let F be an edge-critical graph with chromatic number r + 2. For sufficiently large n, we determine the maximum number of edges in an n-vertex graph with given maximum degree that does not contain a copy of F. Moreover, the unique extremal graph is a complete (r+1)-partite graph.

关键词