Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userErdH{o}s-Gy{a}rf{a}s Conjecture for $P_8$-free graphs
111
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A graph is $P_8$-free if it contains no induced subgraph isomorphic to the path $P_8$ on eight vertices. In 1995, ErdH{o}s and Gy{a}rf{a}s conjectured that every graph of minimum degree at least three contains a cycle whose length is a power of two. In this paper, we confirm the conjecture for $P_8$-free graphs by showing that there exists a cycle of length four or eight in every $P_8$-free graph with minimum degree at least three.
rate research
Read More
For fixed $p$ and $q$, an edge-coloring of the complete graph $K_n$ is said to be a $(p, q)$-coloring if every $K_p$ receives at least $q$ distinct colors. The function $f(n, p, q)$ is the minimum number of colors needed for $K_n$ to have a $(p, q)$-coloring. This function was introduced about 45 years ago, but was studied systematically by ErdH{o}s and Gy{a}rf{a}s in 1997, and is now known as the ErdH{o}s-Gy{a}rf{a}s function. In this paper, we study $f(n, p, q)$ with respect to Gallai-colorings, where a Gallai-coloring is an edge-coloring of $K_n$ without rainbow triangles. Combining the two concepts, we consider the function $g(n, p, q)$ that is the minimum number of colors needed for a Gallai-$(p, q)$-coloring of $K_n$. Using the anti-Ramsey number for $K_3$, we have that $g(n, p, q)$ is nontrivial only for $2leq qleq p-1$. We give a general lower bound for this function and we study how this function falls off from being equal to $n-1$ when $q=p-1$ and $pgeq 4$ to being $Theta(log n)$ when $q = 2$. In particular, for appropriate $p$ and $n$, we prove that $g=n-c$ when $q=p-c$ and $cin {1,2}$, $g$ is at most a fractional power of $n$ when $q=lfloorsqrt{p-1}rfloor$, and $g$ is logarithmic in $n$ when $2leq qleq lfloorlog_2 (p-1)rfloor+1$.
A hole in a graph is an induced cycle of length at least $4$. Let $sge2$ and $tge2$ be integers. A graph $G$ is $(s,t)$-splittable if $V(G)$ can be partitioned into two sets $S$ and $T$ such that $chi(G[S ]) ge s$ and $chi(G[T ]) ge t$. The well-known ErdH{o}s-Lovasz Tihany Conjecture from 1968 states that every graph $G$ with $omega(G) < chi(G) = s + t - 1$ is $(s,t)$-splittable. This conjecture is hard, and few related results are known. However, it has been verified to be true for line graphs, quasi-line graphs, and graphs with independence number $2$. In this paper, we establish more evidence for the ErdH{o}s-Lovasz Tihany Conjecture by showing that every graph $G$ with $alpha(G)ge3$, $omega(G) < chi(G) = s + t - 1$, and no hole of length between $4$ and $2alpha(G)-1$ is $(s,t)$-splittable, where $alpha(G)$ denotes the independence number of a graph $G$.
The ErdH{o}s-Faber-Lov{a}sz conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on $n$ vertices is at most $n$. In this paper, we prove this conjecture for every large $n$. We also provide stabili
An $r$-uniform hypergraph ($r$-graph for short) is called linear if every pair of vertices belong to at most one edge. A linear $r$-graph is complete if every pair of vertices are in exactly one edge. The famous Brown-ErdH{o}s-Sos conjecture states that for every fixed $k$ and $r$, every linear $r$-graph with $Omega(n^2)$ edges contains $k$ edges spanned by at most $(r-2)k+3$ vertices. As an intermediate step towards this conjecture, Conlon and Nenadov recently suggested to prove its natural Ramsey relaxation. Namely, that for every fixed $k$, $r$ and $c$, in every $c$-colouring of a complete linear $r$-graph, one can find $k$ monochromatic edges spanned by at most $(r-2)k+3$ vertices. We prove that this Ramsey version of the conjecture holds under the additional assumption that $r geq r_0(c)$, and we show that for $c=2$ it holds for all $rgeq 4$.
We prove that there exists a function $f(k)=mathcal{O}(k^2 log k)$ such that for every $C_4$-free graph $G$ and every $k in mathbb{N}$, $G$ either contains $k$ vertex-disjoint holes of length at least $6$, or a set $X$ of at most $f(k)$ vertices such that $G-X$ has no hole of length at least $6$. This answers a question of Kim and Kwon [ErdH{o}s-Posa property of chordless cycles and its applications. JCTB 2020].
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
