A path in a properly edge-colored graph is rainbow if its edges have pairwise distinct colors. For a proper edge-coloring $c$ of a graph $G$, let $\operatorname{rpc}(G,c)$ be the minimum number of rainbow paths needed to cover $E(G)$, and let $\operatorname{rpc}(G)$ be the maximum of $\operatorname{rpc}(G,c)$ over all proper edge-colorings of $G$. We prove that, for every fixed $0<\alpha<1$, every properly edge-colored $n$-vertex graph with minimum degree at least $\alpha n$ satisfies $\operatorname{rpc}(G,c)\leq(1+o(1))n/2$, where the coefficient $1/2$ is best possible. We also determine $\operatorname{rpc}(G)$ asymptotically for every complete multipartite graph. If $G=K_{n_1,\ldots,n_r}$ has order $n$ and largest and smallest part sizes $M$ and $s$, respectively, then, uniformly over all choices of the number and sizes of the parts, $\operatorname{rpc}(G)=(1+o(1))\max\{\min\{\lfloor n/2\rfloor,n-M\},(n-s)/2\}$. The proof combines pseudorandom packings of globally rainbow linear forests with a decomposition into dense parts and prescribed avoidance for arbitrary dense graphs, and with reserved connectors and a direct dominant-part argument for complete multipartite graphs.
Let $k\geq2$ be an integer. A $1\bmod k$ edge-coloring of a graph $G$ is an edge-coloring in which every nonzero degree in each color class is congruent to $1$ modulo $k$. Let $\chi'_k(G)$ denote the minimum number of colors required, and let $\chi'_k$ be the supremum of $\chi'_k(G)$ over all finite simple graphs $G$. Botler, Colucci, and Kohayakawa conjectured that there exists an absolute constant $C$ such that $\chi'_k(G)\leq k+C$ for every $k$ and every $G$. We disprove this conjecture, even within the class of bipartite graphs. More precisely, for all integers $c\geq0$ and $k\geq3c+2$, we construct a finite simple bipartite graph $G_{k,c}$ satisfying $\chi'_k(G_{k,c})=k+c+1$. Consequently, $\chi'_k\geq k+\lfloor(k+1)/3\rfloor$ for every $k\geq2$. For $k_m=2\cdot3^{m-1}$, we give an affine-hyperplane construction of a finite simple bipartite graph $G_m$ satisfying $\Delta(G_m)=\chi'_{k_m}(G_m)=3^m=3k_m/2$. More generally, for every sufficiently large $k$, we construct a finite simple bipartite graph $G_k$ such that $\Delta(G_k)=\chi'_k(G_k)\geq3k/2-10(k\log k)^{1/3}$. Our proofs combine a codegree obstruction with explicit cyclic and affine-geometric constructions and a structured random perturbation.
Non-Euclidean spaces inherently enable high-fidelity embeddings for hierarchical and cyclical data due to their geometric properties. Existing approaches unify hyperbolic and spherical embeddings within the framework of constant curvature spaces. However, current methods for Lipschitz regularization remain limited to non-positive curvature geometries, such as hyperbolic and Euclidean spaces, and cannot be naturally extended to the general constant curvature setting. In this paper, we present a rigorous Lipschitz analysis for constant curvature graph convolutional networks ( \(\kappa\) -GCNs) and enhance their robustness through Lipschitz regularization. We derive upper bounds for the Lipschitz constants across constant curvature spaces, thereby standardizing the Lipschitz limits of the \(\kappa\) -stereographic model. Furthermore, we incorporate these bounds into a regularization framework for \(\kappa\) -GCNs to improve stability and robustness. Experimental results demonstrate that the proposed regularization method often strengthens the robustness of \(\kappa\) -GCNs across various curvature regimes, particularly under Gaussian feature noise.
Yang Shi, Jingchao Wang, Liangsi Lu et al.· ACM Transactions on Knowledg...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
