اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA proof of the ErdH{o}s-Faber-Lovasz conjecture
120
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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
قيم البحث
اقرأ أيضاً
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-know
n 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$.
In 1972, Erd{o}s - Faber - Lov{a}sz (EFL) conjectured that, if $textbf{H}$ is a linear hypergraph consisting of $n$ edges of cardinality $n$, then it is possible to color the vertices with $n$ colors so that no two vertices with the same color are in
the same edge. In 1978, Deza, Erd{o}s and Frankl had given an equivalent version of the same for graphs: Let $G= bigcup_{i=1}^{n} A_i$ denote a graph with $n$ complete graphs $A_1, A_2,$ $ dots , A_n$, each having exactly $n$ vertices and have the property that every pair of complete graphs has at most one common vertex, then the chromatic number of $G$ is $n$. The clique degree $d^K(v)$ of a vertex $v$ in $G$ is given by $d^K(v) = |{A_i: v in V(A_i), 1 leq i leq n}|$. In this paper we give a method for assigning colors to the graphs satisfying the hypothesis of the Erdos - Faber - Lovasz conjecture using intersection matrix of the cliques $A_i$s of $G$ and clique degrees of the vertices of $G$. Also, we give theoretical proof of the conjecture for some class of graphs. In particular we show that: 1. If $G$ is a graph satisfying the hypothesis of the Conjecture 1.2 and every $A_i$ ($1 leq i leq n$) has at most $sqrt{n}$ vertices of clique degree greater than 1, then $G$ is $n$-colorable. 2. If $G$ is a graph satisfying the hypothesis of the Conjecture 1.2 and every $A_i$ ($1 leq i leq n$) has at most $left lceil {frac{n+d-1}{d}} right rceil$ vertices of clique degree greater than or equal to $d$ ($2leq d leq n$), then $G$ is $n$-colorable.
For a 2-connected graph $G$ on $n$ vertices and two vertices $x,yin V(G)$, we prove that there is an $(x,y)$-path of length at least $k$ if there are at least $frac{n-1}{2}$ vertices in $V(G)backslash {x,y}$ of degree at least $k$. This strengthens a
well-known theorem due to ErdH{o}s and Gallai in 1959. As the first application of this result, we show that a 2-connected graph with $n$ vertices contains a cycle of length at least $2k$ if it has at least $frac{n}{2}+k$ vertices of degree at least $k$. This confirms a 1975 conjecture made by Woodall. As another applications, we obtain some results which generalize previous theorems of Dirac, ErdH{o}s-Gallai, Bondy, and Fujisawa et al., present short proofs of the path case of Loebl-Koml{o}s-S{o}s Conjecture which was verified by Bazgan et al. and of a conjecture of Bondy on longest cycles (for large graphs) which was confirmed by Fraisse and Fournier, and make progress on a conjecture of Bermond.
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 t
hat 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$.
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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
