ﻻ يوجد ملخص باللغة العربية
Let $c:E(G)to [k]$ be an edge-coloring of a graph $G$, not necessarily proper. For each vertex $v$, let $bar{c}(v)=(a_1,ldots,a_k)$, where $a_i$ is the number of edges incident to $v$ with color $i$. Reorder $bar{c}(v)$ for every $v$ in $G$ in nonincreasing order to obtain $c^*(v)$, the color-blind partition of $v$. When $c^*$ induces a proper vertex coloring, that is, $c^*(u) eq c^*(v)$ for every edge $uv$ in $G$, we say that $c$ is color-blind distinguishing. The minimum $k$ for which there exists a color-blind distinguishing edge coloring $c:E(G)to [k]$ is the color-blind index of $G$, denoted $operatorname{dal}(G)$. We demonstrate that determining the color-blind index is more subtle than previously thought. In particular, determining if $operatorname{dal}(G) leq 2$ is NP-complete. We also connect the color-blind index of a regular bipartite graph to 2-colorable regular hypergraphs and characterize when $operatorname{dal}(G)$ is finite for a class of 3-regular graphs.
An independent transversal of a graph $G$ with a vertex partition $mathcal P$ is an independent set of $G$ intersecting each block of $mathcal P$ in a single vertex. Wanless and Wood proved that if each block of $mathcal P$ has size at least $t$ and
A rainbow matching in an edge-colored graph is a matching in which no two edges have the same color. The color degree of a vertex v is the number of different colors on edges incident to v. Kritschgau [Electron. J. Combin. 27(2020)] studied the exist
Let $G$ be a nonempty simple graph with a vertex set $V(G)$ and an edge set $E(G)$. For every injective vertex labeling $f:V(G)tomathbb{Z}$, there are two induced edge labelings, namely $f^+:E(G)tomathbb{Z}$ defined by $f^+(uv)=f(u)+f(v)$, and $f^-:E
Tuza [1992] proved that a graph with no cycles of length congruent to $1$ modulo $k$ is $k$-colorable. We prove that if a graph $G$ has an edge $e$ such that $G-e$ is $k$-colorable and $G$ is not, then for $2leq rleq k$, the edge $e$ lies in at least
Let $G=(V,E)$ be a finite connected graph along with a coloring of the vertices of $G$ using the colors in a given set $X$. In this paper, we introduce multi-color forcing, a generalization of zero-forcing on graphs, and give conditions in which the