Maximum diameter of 3‐ and 4‐colorable graphs | Zendy

Czabarka Éva | Zendy; Smith Stephen J. | Zendy; Székely László | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research