اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدC4-free subgraphs with large average degree
79
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Motivated by a longstanding conjecture of Thomassen, we study how large the average degree of a graph needs to be to imply that it contains a $C_4$-free subgraph with average degree at least $t$. Kuhn and Osthus showed that an average degree bound which is double exponential in t is sufficient. We give a short proof of this bound, before reducing it to a single exponential. That is, we show that any graph $G$ with average degree at least $2^{ct^2log t}$ (for some constant $c>0$) contains a $C_4$-free subgraph with average degree at least $t$. Finally, we give a construction which improves the lower bound for this problem, showing that this initial average degree must be at least $t^{3-o(1)}$.
قيم البحث
اقرأ أيضاً
Answering some questions of Gutman, we show that, except for four specific trees, every connected graph G of order n, with no cycle of order 4 and with maximum degree at most 3, has energy greater that its order. Here, the energy of a graph is the su
m of the moduli of its eigenvalues. We give more general theorems and state two conjectures.
A rainbow matching in an edge-colored graph is a matching in which no two edges have the same color. The color degree of a vertex v is the number of different colors on edges incident to v. Kritschgau [Electron. J. Combin. 27(2020)] studied the exist
ence of rainbow matchings in edge-colored graph G with average color degree at least 2k, and proved some sufficient conditions for a rainbow marching of size k in G. The sufficient conditions include that |V(G)|>=12k^2+4k, or G is a properly edge-colored graph with |V(G)|>=8k. In this paper, we show that every edge-colored graph G with |V(G)|>=4k-4 and average color degree at least 2k-1 contains a rainbow matching of size k. In addition, we also prove that every strongly edge-colored graph G with average degree at least 2k-1 contains a rainbow matching of size at least k. The bound is sharp for complete graphs.
A hereditary class of graphs $mathcal{G}$ is emph{$chi$-bounded} if there exists a function $f$ such that every graph $G in mathcal{G}$ satisfies $chi(G) leq f(omega(G))$, where $chi(G)$ and $omega(G)$ are the chromatic number and the clique number o
f $G$, respectively. As one of the first results about $chi$-bounded classes, Gy{a}rf{a}s proved in 1985 that if $G$ is $P_t$-free, i.e., does not contain a $t$-vertex path as an induced subgraph, then $chi(G) leq (t-1)^{omega(G)-1}$. In 2017, Chudnovsky, Scott, and Seymour proved that $C_{geq t}$-free graphs, i.e., graphs that exclude induced cycles with at least $t$ vertices, are $chi$-bounded as well, and the obtained bound is again superpolynomial in the clique number. Note that $P_{t-1}$-free graphs are in particular $C_{geq t}$-free. It remains a major open problem in the area whether for $C_{geq t}$-free, or at least $P_t$-free graphs $G$, the value of $chi(G)$ can be bounded from above by a polynomial function of $omega(G)$. We consider a relaxation of this problem, where we compare the chromatic number with the size of a largest balanced biclique contained in the graph as a (not necessarily induced) subgraph. We show that for every $t$ there exists a constant $c$ such that for and every $C_{geq t}$-free graph which does not contain $K_{ell,ell}$ as a subgraph, it holds that $chi(G) leq ell^{c}$.
We extend the classical stability theorem of Erdos and Simonovits for forbidden graphs of logarithmic order.
In 1994, ErdH{o}s, Gy{a}rf{a}s and {L}uczak posed the following problem: given disjoint vertex sets $V_1,dots,V_n$ of size~$k$, with exactly one edge between any pair $V_i,V_j$, how large can $n$ be such that there will always be an independent trans
versal? They showed that the maximal $n$ is at most $(1+o(1))k^2$, by providing an explicit construction with these parameters and no independent transversal. They also proved a lower bound which is smaller by a $2e$-factor. In this paper, we solve this problem by showing that their upper bound construction is best possible: if $nle (1-o(1))k^2$, there will always be an independent transversal. In fact, this result is a very special case of a much more general theorem which concerns independent transversals in arbitrary partite graphs that are `locally sparse, meaning that the maximum degree between each pair of parts is relatively small. In this setting, Loh and Sudakov provided a global emph{maximum} degree condition for the existence of an independent transversal. We show that this can be relaxed to an emph{average} degree condition. We can also use our new theorem to establish tight bounds for a more general version of the ErdH{o}s--Gy{a}rf{a}s--{L}uczak problem and solve a conjecture of Yuster from 1997. This exploits a connection to the Turan numbers of complete bipartite graphs, which might be of independent interest. Finally, we discuss some partial results on the hypergraph variant of the problem, and formulate a conjecture in this case.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
