Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA proof of the ErdH{o}s-Faber-Lovasz conjecture
120
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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
rate research
Read More
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$.
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 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$.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
