Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStrong edge-colorings of sparse graphs with large maximum degree
208
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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).
rate research
Read More
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 digraph $D$ with $m $ arcs, a bijection $tau: A(D)rightarrow {1, 2, ldots, m}$ is an antimagic labeling of $D$ if no two vertices in $D$ have the same vertex-sum, where the vertex-sum of a vertex $u $ in $D$ under $tau$ is the sum of labels of all arcs entering $u$ minus the sum of labels of all arcs leaving $u$. We say $(D, tau)$ is an antimagic orientation of a graph $G$ if $D$ is an orientation of $G$ and $tau$ is an antimagic labeling of $D$. Motivated by the conjecture of Hartsfield and Ringel from 1990 on antimagic labelings of graphs, Hefetz, M{u}tze, and Schwartz in 2010 initiated the study of antimagic orientations of graphs, and conjectured that every connected graph admits an antimagic orientation. This conjecture seems hard, and few related results are known. However, it has been verified to be true for regular graphs and biregular bipartite graphs. In this paper, we prove that every connected graph $G$ on $nge9$ vertices with maximum degree at least $n-5$ admits an antimagic orientation.
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.
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$.
A $k$-improper edge coloring of a graph $G$ is a mapping $alpha:E(G)longrightarrow mathbb{N}$ such that at most $k$ edges of $G$ with a common endpoint have the same color. An improper edge coloring of a graph $G$ is called an improper interval edge coloring if the colors of the edges incident to each vertex of $G$ form an integral interval. In this paper we introduce and investigate a new notion, the interval coloring impropriety (or just impropriety) of a graph $G$ defined as the smallest $k$ such that $G$ has a $k$-improper interval edge coloring; we denote the smallest such $k$ by $mu_{mathrm{int}}(G)$. We prove upper bounds on $mu_{mathrm{int}}(G)$ for general graphs $G$ and for particular families such as bipartite, complete multipartite and outerplanar graphs; we also determine $mu_{mathrm{int}}(G)$ exactly for $G$ belonging to some particular classes of graphs. Furthermore, we provide several families of graphs with large impropriety; in particular, we prove that for each positive integer $k$, there exists a graph $G$ with $mu_{mathrm{int}}(G) =k$. Finally, for graphs with at least two vertices we prove a new upper bound on the number of colors used in an improper interval edge coloring.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
