Premium
Regular graphs with prescribed chromatic number
Author(s) -
Caccetta L.,
Pullman N. J.
Publication year - 1990
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190140107
Subject(s) - combinatorics , mathematics , chromatic scale , conjecture , graph , discrete mathematics , induced subgraph , vertex (graph theory)
We determine the minimum number of edges in a regular connected graph on n vertices, containing a complete subgraph of order k ≤ n /2. This enables us to confirm and strengthen a conjecture of P. Erdös on the existence of regular graphs with prescribed chromatic number.