Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userColor-blind index in graphs of very low degree
115
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 the average degree of vertices in each block is at most $t/4$, then an independent transversal of $mathcal P$ exists. We present a construction showing that this result is optimal: for any $varepsilon > 0$ and sufficiently large $t$, there is a family of forests with vertex partitions whose block size is at least $t$, average degree of vertices in each block is at most $(frac14+varepsilon)t$, and there is no independent transversal. This unexpectedly shows that methods related to entropy compression such as the Rosenfeld-Wanles-Wood scheme or the Local Cut Lemma are tight for this problem. Further constructions are given for variants of the problem, including the hypergraph version.
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 existence of rainbow matchings in edge-colored graph G with average color degree at least 2k, and proved some sufficient conditions for a rainbow marching of size k in G. The sufficient conditions include that |V(G)|>=12k^2+4k, or G is a properly edge-colored graph with |V(G)|>=8k. In this paper, we show that every edge-colored graph G with |V(G)|>=4k-4 and average color degree at least 2k-1 contains a rainbow matching of size k. In addition, we also prove that every strongly edge-colored graph G with average degree at least 2k-1 contains a rainbow matching of size at least k. The bound is sharp for complete graphs.
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(G)tomathbb{Z}$ defined by $f^-(uv)=|f(u)-f(v)|$. The sum index and the difference index are the minimum cardinalities of the ranges of $f^+$ and $f^-$, respectively. We provide upper and lower bounds on the sum index and difference index, and determine the sum index and difference index of various families of graphs. We also provide an interesting conjecture relating the sum index and the difference index of graphs.
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 $prod_{i=1}^{r-1}(k-i)$ cycles of length $1mod r$ in $G$, and $G-e$ contains at least $frac{1}{2}prod_{i=1}^{r-1}(k-i)$ cycles of length $0 mod r$. A $(k,d)$-coloring of $G$ is a homomorphism from $G$ to the graph $K_{k:d}$ with vertex set $mathbb{Z}_{k}$ defined by making $i$ and $j$ adjacent if $dleq j-i leq k-d$. When $k$ and $d$ are relatively prime, define $s$ by $sdequiv 1mod k$. A result of Zhu [2002] implies that $G$ is $(k,d)$-colorable when $G$ has no cycle $C$ with length congruent to $is$ modulo $k$ for any $iin {1,ldots,2d-1}$. In fact, only $d$ classes need be excluded: we prove that if $G-e$ is $(k,d)$-colorable and $G$ is not, then $e$ lies in at least one cycle with length congruent to $ismod k$ for some $i$ in ${1,ldots,d}$. Furthermore, if this does not occur with $iin{1,ldots,d-1}$, then $e$ lies in at least two cycles with length $1mod k$ and $G-e$ contains a cycle of length $0 mod k$.
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 multi-color forcing process terminates regardless of the number of colors used. We give an upper bound on the number of steps required to terminate a forcing procedure in terms of the number of vertices in the graph on which the procedure is being applied. We then focus on multi-color forcing with three colors and analyze the end states of certain families of graphs, including complete graphs, complete bipartite graphs, and paths, based on various initial colorings. We end with a few directions for future research.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
