Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSparse halves in $K_4$-free graphs
140
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A conjecture of Chung and Graham states that every $K_4$-free graph on $n$ vertices contains a vertex set of size $lfloor n/2 rfloor$ 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.
rate research
Read More
Kostochka and Yancey resolved a famous conjecture of Ore on the asymptotic density of $k$-critical graphs by proving that every $k$-critical graph $G$ satisfies $|E(G)| geq (frac{k}{2} - frac{1}{k-1})|V(G)| - frac{k(k-3)}{2(k-1)}$. The class of graphs for which this bound is tight, $k$-Ore graphs, contain a notably large number of $K_{k-2}$-subgraphs. Subsequent work attempted to determine the asymptotic density for $k$-critical graphs that do emph{not} contain large cliques as subgraphs, but only partial progress has been made on this problem. The second author showed that if $G$ is 5-critical and has no $K_3$-subgraphs, then for $varepsilon = 1/84$, $|E(G)| geq (frac{9}{4} + varepsilon)|V(G)| - frac{5}{4}$. It has also been shown that for all $k geq 33$, there exists $varepsilon_k > 0$ such that $k$-critical graphs with no $K_{k-2}$-subgraphs satisfy $|E(G)| geq (frac{k}{2} - frac{1}{k-1} + varepsilon_k)|V(G)| - frac{k(k-3)}{2(k-1)}$. In this work, we develop general structural results that are applicable to resolving the remaining difficult cases $6 leq k leq 32$. We apply our results to carefully analyze the structure of 6-critical graphs and use a discharging argument to show that for $varepsilon_6 = 1/1050$, 6-critical graphs with no $K_4$ subgraph satisfy $|E(G)| geq ( frac{k}{2} - frac{1}{k-1} + varepsilon_6 ) |V(G)| - frac{k(k-3)}{2(k-1)}$.
Given two graphs $H_1$ and $H_2$, a graph $G$ is $(H_1,H_2)$-free if it contains no induced subgraph isomorphic to $H_1$ or $H_2$. Let $P_t$ be the path on $t$ vertices. A graph $G$ is $k$-vertex-critical if $G$ has chromatic number $k$ but every proper induced subgraph of $G$ has chromatic number less than $k$. The study of $k$-vertex-critical graphs for graph classes is an important topic in algorithmic graph theory because if the number of such graphs that are in a given hereditary graph class is finite, then there is a polynomial-time algorithm to decide if a graph in the class is $(k-1)$-colorable. In this paper, we initiate a systematic study of the finiteness of $k$-vertex-critical graphs in subclasses of $P_5$-free graphs. Our main result is a complete classification of the finiteness of $k$-vertex-critical graphs in the class of $(P_5,H)$-free graphs for all graphs $H$ on 4 vertices. To obtain the complete dichotomy, we prove the finiteness for four new graphs $H$ using various techniques -- such as Ramsey-type arguments and the dual of Dilworths Theorem -- that may be of independent interest.
We prove that for any $tge 3$ there exist constants $c>0$ and $n_0$ such that any $d$-regular $n$-vertex graph $G$ with $tmid ngeq n_0$ and second largest eigenvalue in absolute value $lambda$ satisfying $lambdale c d^{t}/n^{t-1}$ contains a $K_t$-factor, that is, vertex-disjoint copies of $K_t$ covering every vertex of $G$.
Recently, Kostochka and Yancey proved that a conjecture of Ore is asymptotically true by showing that every $k$-critical graph satisfies $|E(G)|geqleftlceilleft(frac{k}{2}-frac{1}{k-1}right)|V(G)|-frac{k(k-3)}{2(k-1)}rightrceil.$ They also characterized the class of graphs that attain this bound and showed that it is equivalent to the set of $k$-Ore graphs. We show that for any $kgeq33$ there exists an $varepsilon>0$ so that if $G$ is a $k$-critical graph, then $|E(G)|geqleft(frac{k}{2}-frac{1}{k-1}+varepsilon_kright)|V(G)|-frac{k(k-3)}{2(k-1)}-(k-1)varepsilon T(G)$, where $T(G)$ is a measure of the number of disjoint $K_{k-1}$ and $K_{k-2}$ subgraphs in $G$. This also proves for $kgeq33$ the following conjecture of Postle regarding the asymptotic density: For every $kgeq4$ there exists an $varepsilon_k>0$ such that if $G$ is a $k$-critical $K_{k-2}$-free graph, then $|E(G)|geq left(frac{k}{2}-frac{1}{k-1}+varepsilon_kright)|V(G)|-frac{k(k-3)}{2(k-1)}$. As a corollary, our result shows that the number of disjoint $K_{k-2}$ subgraphs in a $k$-Ore graph scales linearly with the number of vertices and, further, that the same is true for graphs whose number of edges is close to Kostochka and Yanceys bound.
For all $nge 9$, we show that the only triangle-free graphs on $n$ vertices maximizing the number $5$-cycles are balanced blow-ups of a 5-cycle. This completely resolves a conjecture by ErdH{o}s, and extends results by Grzesik and Hatami, Hladky, Kr{a}l, Norin and Razborov, where they independently showed this same result for large $n$ and for all $n$ divisible by $5$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
