Premium
Order plus size of τ ‐critical graphs
Author(s) -
Gyárfás András,
Lehel Jenő
Publication year - 2021
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.22603
Subject(s) - mathematics , combinatorics , upper and lower bounds , graph , order (exchange) , discrete mathematics , finance , economics , mathematical analysis
Abstract Let G = ( V , E ) be a τ ‐critical graph with τ ( G ) = t . Erdős and Gallai proved that ∣ V ∣ ≤ 2 t and the bound ∣ E ∣ ≤t + 1 2was obtained by Erdős, Hajnal, and Moon. We give here the sharp combined bound ∣ E ∣ + ∣ V ∣ ≤t + 2 2and find all graphs with equality.