Graphs with large maximum degree containing no edge-critical graphs

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish
Article number103576
JournalEuropean Journal of Combinatorics
Volume106
DOIs
StatePublished - Dec 2022

Fingerprint

Dive into the research topics of 'Graphs with large maximum degree containing no edge-critical graphs'. Together they form a unique fingerprint.

Cite this