In this paper, we study proper and complete edge-colorings of Johnson graphs $J(n,2)$, also called $n$-triangular graphs. They are isomorphic both to the 2-token graphs of complete graphs and to the line graphs of complete graphs. A $t$-edge-coloring of a graph $G$ is a function that assigns one color from $\{1,2,\ldots,t\}$ to each edge. Such a coloring is called proper if no two incident edges receive the same color, and complete if every pair of distinct colors appears on a pair of incident edges. The achromatic index, denoted by $\alpha_2(G)$, is the largest integer $t$ for which $G$ admits a proper and complete $t$-edge-coloring. We establish new lower and upper bounds for $\alpha_2(J(n,2))$, provide explicit proper and complete edge-colorings attaining the lower bounds, and determine the exact value of $\alpha_2(J(n,2))$ for several values of $n$.
For an integer $k\geq2$, let $\chi_k'(G)$ denote the minimum number of colors in an edge-coloring of a graph $G$ such that every nonzero degree in each color subgraph is congruent to $1\pmod{k}$. A graph is a $0_k$-graph if every vertex degree is divisible by $k$. We disprove a conjecture of Berthe et al.\ (On modular...
Let $G$ be a graph with minimum degree $\delta(G)\ge|V(G)|/2$. Can we color the edges of $G$ with red and blue so that every pair of non-adjacent vertices is connected by a path consisting of exactly one red edge and one blue edge? We provide an affirmative answer to this question for a class of graphs that are ``close...
J'anos Bar'at, Simona Boyadzhiyska, Andrea Freschi· 0 citations
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...
We study the size of the largest monochromatic connected component that must appear in any edge-coloring of a random graph. Let $G\sim G(n,p)$ with $p\gg 1/n$ and $p=o(1)$, and write $np=he^h$. We show that, with high probability, every $2$-edge-coloring of $G$ contains a monochromatic connected component of order at l...
For finite simple graphs $G,H$ on a common vertex set $V$, we say that $H$ is $G$-colorable if $H$ admits a proper list coloring with list assignment $L(v)=N_G(v)$ for all $v\in V$. This notion of coloring a graph using the neighborhood of another graph on the same vertex set, which we call \emph{graphic list coloring}...
For a graph $G$, a proper edge coloring of $G$ is called a D-coloring if every diamond subgraph of $G$ is rainbow. Let $\chi'_D(G)$ be the D-chromatic index of $G$, which is the smallest integer $k$ such that $G$ admits a D-coloring with $k$ colors. Let $\Delta$ be the maximum degree of $G$. The only known Brooks-type...
Lin Tian, Run-Ze Wang· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
