Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn improved upper bound on the adjacent vertex distinguishing chromatic index of a graph
265
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
An adjacent vertex distinguishing coloring of a graph G is a proper edge coloring of G such that any pair of adjacent vertices are incident with distinct sets of colors. The minimum number of colors needed for an adjacent vertex distinguishing coloring of G is denoted by $chi_a(G)$. In this paper, we prove that $chi_a(G)$ <= 5($Delta+2$)/2 for any graph G having maximum degree $Delta$ and no isolated edges. This improves a result in [S. Akbari, H. Bidkhori, N. Nosrati, r-Strong edge colorings of graphs, Discrete Math. 306 (2006), 3005-3010], which states that $chi_a(G)$ <= 3$Delta$ for any graph G without isolated edges.
rate research
Read More
The Wiener index of a connected graph is the summation of all distances between unordered pairs of vertices of the graph. In this paper, we give an upper bound on the Wiener index of a $k$-connected graph $G$ of order $n$ for integers $n-1>k ge 1$: [W(G) le frac{1}{4} n lfloor frac{n+k-2}{k} rfloor (2n+k-2-klfloor frac{n+k-2}{k} rfloor).] Moreover, we show that this upper bound is sharp when $k ge 2$ is even, and can be obtained by the Wiener index of Harary graph $H_{k,n}$.
In this note we obtain a new bound for the acyclic edge chromatic number $a(G)$ of a graph $G$ with maximum degree $D$ proving that $a(G)leq 3.569(D-1)$. To get this result we revisit and slightly modify the method described in [Giotis, Kirousis, Psaromiligkos and Thilikos, Theoretical Computer Science, 66: 40-50, 2017].
A $k$-proper edge-coloring of a graph G is called adjacent vertex-distinguishing if any two adjacent vertices are distinguished by the set of colors appearing in the edges incident to each vertex. The smallest value $k$ for which $G$ admits such coloring is denoted by $chi_a(G)$. We prove that $chi_a(G) = 2R + 1$ for most circulant graphs $C_n([1, R])$.
The strong chromatic index of a graph $G$, denoted $chi_s(G)$, is the least number of colors needed to edge-color $G$ so that edges at distance at most two receive distinct colors. The strong list chromatic index, denoted $chi_{s,ell}(G)$, is the least integer $k$ such that if arbitrary lists of size $k$ are assigned to each edge then $G$ can be edge-colored from those lists where edges at distance at most two receive distinct colors. We use the discharging method, the Combinatorial Nullstellensatz, and computation to show that if $G$ is a subcubic planar graph with $operatorname{girth}(G) geq 41$ then $chi_{s,ell}(G) leq 5$, answering a question of Borodin and Ivanova [Precise upper bound for the strong edge chromatic number of sparse planar graphs, Discuss. Math. Graph Theory, 33(4), (2014) 759--770]. We further show that if $G$ is a subcubic planar graph and $operatorname{girth}(G) geq 30$, then $chi_s(G) leq 5$, improving a bound from the same paper. Finally, if $G$ is a planar graph with maximum degree at most four and $operatorname{girth}(G) geq 28$, then $chi_s(G) leq 7$, improving a more general bound of Wang and Zhao from [Odd graphs and its application on the strong edge coloring, arXiv:1412.8358] in this case.
The $chi$-stability index ${rm es}_{chi}(G)$ of a graph $G$ is the minimum number of its edges whose removal results in a graph with the chromatic number smaller than that of $G$. In this paper three open problems from [European J. Combin. 84 (2020) 103042] are considered. Examples are constructed which demonstrate that a known characterization of $k$-regular ($kle 5$) graphs $G$ with ${rm es}_{chi}(G) = 1$ does not extend to $kge 6$. Graphs $G$ with $chi(G)=3$ for which ${rm es}_{chi}(G)+{rm es}_{chi}(overline{G}) = 2$ holds are characterized. Necessary conditions on graphs $G$ which attain a known upper bound on ${rm es}_{chi}(G)$ in terms of the order and the chromatic number of $G$ are derived. The conditions are proved to be sufficient when $nequiv 2 pmod 3$ and $chi(G)=3$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
