Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userList strong edge-coloring of graphs with maximum degree 4
154
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
If the vertices of a graph $G$ are colored with $k$ colors such that no adjacent vertices receive the same color and the sizes of any two color classes differ by at most one, then $G$ is said to be equitably $k$-colorable. Let $|G|$ denote the number of vertices of $G$ and $Delta=Delta(G)$ the maximum degree of a vertex in $G$. We prove that a graph $G$ of order at least 6 is equitably $Delta$-colorable if $G$ satisfies $(|G|+1)/3 leq Delta < |G|/2$ and none of its components is a $K_{Delta +1}$.
A {em strong $k$-edge-coloring} of a graph $G$ is a mapping from $E(G)$ to ${1,2,ldots,k}$ such that every two adjacent edges or two edges adjacent to the same edge receive distinct colors. The {em strong chromatic index} $chi_s(G)$ of a graph $G$ is the smallest integer $k$ such that $G$ admits a strong $k$-edge-coloring. We give bounds on $chi_s(G)$ in terms of the maximum degree $Delta(G)$ of a graph $G$. when $G$ is sparse, namely, when $G$ is $2$-degenerate or when the maximum average degree ${rm Mad}(G)$ is small. We prove that the strong chromatic index of each $2$-degenerate graph $G$ is at most $5Delta(G) +1$. Furthermore, we show that for a graph $G$, if ${rm Mad}(G)< 8/3$ and $Delta(G)geq 9$, then $chi_s(G)leq 3Delta(G) -3$ (the bound $3Delta(G) -3$ is sharp) and if ${rm Mad}(G)<3$ and $Delta(G)geq 7$, then $chi_s(G)leq 3Delta(G)$ (the restriction ${rm Mad}(G)<3$ is sharp).
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.
Motivated by the ErdH{o}s-Faber-Lovasz (EFL) conjecture for hypergraphs, we consider the list edge coloring of linear hypergraphs. We discuss several conjectures for list edge coloring linear hypergraphs that generalize both EFL and Vizings theorem for graphs. For example, we conjecture that in a linear hypergraph of rank 3, the list edge chromatic number is at most 2 times the maximum degree plus 1. We show that for sufficiently large fixed rank and sufficiently large degree, the conjectures are true.
An incidence of an undirected graph G is a pair $(v,e)$ where $v$ is a vertex of $G$ and $e$ an edge of $G$ incident with $v$. Two incidences $(v,e)$ and $(w,f)$ are adjacent if one of the following holds: (i) $v = w$, (ii) $e = f$ or (iii) $vw = e$ or $f$. An incidence coloring of $G$ assigns a color to each incidence of $G$ in such a way that adjacent incidences get distinct colors. In 2005, Hosseini Dolama emph{et al.}~citep{ds05} proved that every graph with maximum average degree strictly less than $3$ can be incidence colored with $Delta+3$ colors. Recently, Bonamy emph{et al.}~citep{Bonamy} proved that every graph with maximum degree at least $4$ and with maximum average degree strictly less than $frac{7}{3}$ admits an incidence $(Delta+1)$-coloring. In this paper we give bounds for the number of colors needed to color graphs having maximum average degrees bounded by different values between $4$ and $6$. In particular we prove that every graph with maximum degree at least $7$ and with maximum average degree less than $4$ admits an incidence $(Delta+3)$-coloring. This result implies that every triangle-free planar graph with maximum degree at least $7$ is incidence $(Delta+3)$-colorable. We also prove that every graph with maximum average degree less than 6 admits an incidence $(Delta + 7)$-coloring. More generally, we prove that $Delta+k-1$ colors are enough when the maximum average degree is less than $k$ and the maximum degree is sufficiently large.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
