Premium
Maximum diameter of 3‐ and 4‐colorable graphs
Author(s) -
Czabarka Éva,
Smith Stephen J.,
Székely László
Publication year - 2023
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.22869
Subject(s) - mathematics , combinatorics , induced subgraph , degree (music) , order (exchange) , discrete mathematics , graph , physics , finance , vertex (graph theory) , acoustics , economics
Abstract Erdős et al. made conjectures for the maximum diameter of connected graphs without a complete subgraphK k + 1${K}_{k+1}$ , which have ordern $n$ and minimum degreeδ $\delta $ . Settling a weaker version of a problem, by strengthening theK k + 1${K}_{k+1}$ ‐free condition tok $k$ ‐colorable, we solve the problem fork = 3 $k=3$ andk = 4 $k=4$ using a unified linear programming duality approach. The casek = 4 $k=4$ is a substantial simplification of the result of Czabarka et al.