Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEdge coloring graphs with large minimum degree
97
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $G$ be a simple graph with maximum degree $Delta(G)$. A subgraph $H$ of $G$ is overfull if $|E(H)|>Delta(G)lfloor |V(H)|/2 rfloor$. Chetwynd and Hilton in 1985 conjectured that a graph $G$ with $Delta(G)>|V(G)|/3$ has chromatic index $Delta(G)$ if and only if $G$ contains no overfull subgraph. The 1-factorization conjecture is a special case of this overfull conjecture, which states that for even $n$, every regular $n$-vertex graph with degree at least about $n/2$ has a 1-factorization and was confirmed for large graphs in 2014. Supporting the overfull conjecture as well as generalizing the 1-factorization conjecture in an asymptotic way, in this paper, we show that for any given $0<varepsilon <1$, there exists a positive integer $n_0$ such that the following statement holds: if $G$ is a graph on $2nge n_0$ vertices with minimum degree at least $(1+varepsilon)n$, then $G$ has chromatic index $Delta(G)$ if and only if $G$ contains no overfull subgraph.
rate research
Read More
A fundamental theorem of Wilson states that, for every graph $F$, every sufficiently large $F$-divisible clique has an $F$-decomposition. Here a graph $G$ is $F$-divisible if $e(F)$ divides $e(G)$ and the greatest common divisor of the degrees of $F$ divides the greatest common divisor of the degrees of $G$, and $G$ has an $F$-decomposition if the edges of $G$ can be covered by edge-disjoint copies of $F$. We extend this result to graphs $G$ which are allowed to be far from complete. In particular, together with a result of Dross, our results imply that every sufficiently large $K_3$-divisible graph of minimum degree at least $9n/10+o(n)$ has a $K_3$-decomposition. This significantly improves previous results towards the long-standing conjecture of Nash-Williams that every sufficiently large $K_3$-divisible graph with minimum degree at least $3n/4$ has a $K_3$-decomposition. We also obtain the asymptotically correct minimum degree thresholds of $2n/3 +o(n)$ for the existence of a $C_4$-decomposition, and of $n/2+o(n)$ for the existence of a $C_{2ell}$-decomposition, where $ellge 3$. Our main contribution is a general `iterative absorption method which turns an approximate or fractional decomposition into an exact one. In particular, our results imply that in order to prove an asymptotic version of Nash-Williams conjecture, it suffices to show that every $K_3$-divisible graph with minimum degree at least $3n/4+o(n)$ has an approximate $K_3$-decomposition,
A strong edge-coloring of a graph $G$ is an edge-coloring such that any two edges on a path of length three receive distinct colors. We denote the strong chromatic index by $chi_{s}(G)$ which is the minimum number of colors that allow a strong edge-coloring of $G$. ErdH{o}s and Nev{s}etv{r}il conjectured in 1985 that the upper bound of $chi_{s}(G)$ is $frac{5}{4}Delta^{2}$ when $Delta$ is even and $frac{1}{4}(5Delta^{2}-2Delta +1)$ when $Delta$ is odd, where $Delta$ is the maximum degree of $G$. The conjecture is proved right when $Deltaleq3$. The best known upper bound for $Delta=4$ is 22 due to Cranston previously. In this paper we extend the result of Cranston to list strong edge-coloring, that is to say, we prove that when $Delta=4$ the upper bound of list strong chromatic index is 22.
Given a simple graph $G$, denote by $Delta(G)$, $delta(G)$, and $chi(G)$ the maximum degree, the minimum degree, and the chromatic index of $G$, respectively. We say $G$ is emph{$Delta$-critical} if $chi(G)=Delta(G)+1$ and $chi(H)le Delta(G)$ for every proper subgraph $H$ of $G$; and $G$ is emph{overfull} if $|E(G)|>Delta lfloor |V(G)|/2 rfloor$. Since a maximum matching in $G$ can have size at most $lfloor |V(G)|/2 rfloor$, it follows that $chi(G) = Delta(G) +1$ if $G$ is overfull. Conversely, let $G$ be a $Delta$-critical graph. The well known overfull conjecture of Chetwynd and Hilton asserts that $G$ is overfull provided $Delta(G) > |V(G)|/3$. In this paper, we show that any $Delta$-critical graph $G$ is overfull if $Delta(G) - 7delta(G)/4ge(3|V(G)|-17)/4$.
This paper presents sufficient conditions for Hamiltonian paths and cycles in graphs. Letting $lambdaleft( Gright) $ denote the spectral radius of the adjacency matrix of a graph $G,$ the main results of the paper are: (1) Let $kgeq1,$ $ngeq k^{3}/2+k+4,$ and let $G$ be a graph of order $n$, with minimum degree $deltaleft( Gright) geq k.$ If [ lambdaleft( Gright) geq n-k-1, ] then $G$ has a Hamiltonian cycle, unless $G=K_{1}vee(K_{n-k-1}+K_{k})$ or $G=K_{k}vee(K_{n-2k}+overline{K}_{k})$. (2) Let $kgeq1,$ $ngeq k^{3}/2+k^{2}/2+k+5,$ and let $G$ be a graph of order $n$, with minimum degree $deltaleft( Gright) geq k.$ If [ lambdaleft( Gright) geq n-k-2, ] then $G$ has a Hamiltonian path, unless $G=K_{k}vee(K_{n-2k-1}+overline {K}_{k+1})$ or $G=K_{n-k-1}+K_{k+1}$ In addition, it is shown that in the above statements, the bounds on $n$ are tight within an additive term not exceeding $2$.
The degree-based entropy of a graph is defined as the Shannon entropy based on the information functional that associates the vertices of the graph with the corresponding degrees. In this paper, we study extremal problems of finding the graphs attaining the minimum degree-based graph entropy among graphs and bipartite graphs with a given number of vertices and edges. We characterize the unique extremal graph achieving the minimum value among graphs with a given number of vertices and edges and present a lower bound for the degree-based entropy of bipartite graphs and characterize all the extremal graphs which achieve the lower bound. This implies the known result due to Cao et al. (2014) that the star attains the minimum value of the degree-based entropy among trees with a given number of vertices.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
