Premium
Sparse halves in K 4 ‐free graphs
Author(s) -
Liu Xizhi,
Ma Jie
Publication year - 2022
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.22722
Subject(s) - combinatorics , mathematics , conjecture , vertex (graph theory) , graph , discrete mathematics
Abstract A conjecture of Chung and Graham states that every K 4 ‐free graph on n vertices contains a vertex set of size ⌊ n ∕ 2 ⌋ that spans at most n 2 ∕ 18 edges. We make the first step toward this conjecture by showing that it holds for all regular graphs.