A B-coloring of a graph $G$ is a proper edge-coloring in which every $4$-cycle is rainbow. Let $q_B(G)$ be the minimum number of colors in such a coloring. Gy\'arf\'as and S\'ark\"ozy (2023) determine $q_B(G)$ when $G=P_m\square P_n$ is a rectangular grid. In this paper, we completely determine $q_B(G)$ for cylindrical and torus grid graphs $G$. For a torus grid $G=C_m\square C_n$, where $m,n\ge3$ are integers, we prove that $q_B(G)=4=\Delta(G)$ if both $m$ and $n$ are even and $G\not\cong C_4\square C_{4k+2}$ for any integer $k\ge1$, and that $q_B(G)=5=\Delta(G)+1$ if at least one of $m,n$ is odd or $G\cong C_4\square C_{4k+2}$ for some integer $k\ge1$. For a cylindrical grid $G=C_s\square P_m$, $q_B(G)$ also depends on the parity of $s$ and the length of $P_m$. For integers $m\ge2$ and $n\ge2$, we have $q_B(C_{2n}\square P_m)=4$. For integers $m\ge2$ and $n\ge1$, we have $q_B(C_{2n+1}\square P_m)=4$ if $2\le m\le n$, whereas $q_B(C_{2n+1}\square P_m)=5$ if $m\ge n+1$. In higher dimensions, we discuss the B-coloring of discrete torus and $\ell$-cylindrical grid, obtaining some exact results and certain bounds.
A B-coloring of a graph $G$ is a proper edge-coloring in which every $4$-cycle receives four distinct colors; let $q_B(G)$ be the minimum number of colors in such a coloring. Every graph of maximum degree $\Delta$ is $K_{2,\Delta+1}$-free; hence the known $2\Delta$ bound for planar graphs with $\Delta\ge38$ (Kong et al., 2026) motivates our study of $K_{2,t}$-free planar graphs, where $t\ge2$ is an integer. We prove $q_B(G)=\Delta(G)$ when $t=2$ and $\Delta(G)\ge7$, or when $t\ge3$ and $\Delta(G)\ge14(t-1)$. For $t\ge35$, the bound $q_B(G)\le\Delta(G)+t-1$ holds regardless of $\Delta(G)$; for every $t\ge2$, it also holds when $\Delta(G)>428$. Finally, for every integer $k\ge1$, every $k$-degenerate $K_{2,t}$-free graph satisfies $q_B(G)\le\Delta(G)+(k-1)\min\{t-1,\Delta(G)\}$, with equality for $K_{k,t-1}$ when $k\ge2$ and $t-1\ge k$.
A $B$-coloring of a graph is a proper edge-coloring in which every $4$-cycle is rainbow, and $q_B(G)$ denotes the minimum number of colors in such a coloring. Let $\Delta_2(G)$ denote the maximum number of common neighbors of two distinct vertices of $G$. We prove that, for integers $1\le d\le\Delta$, every finite simple $d$-degenerate graph $G$ with $\Delta(G)\le\Delta$ satisfies $$q_B(G)\le \Delta+(d-1)\Delta_2(G)\le d\Delta.$$ Consequently, $d\Delta$ is the exact maximum, with equality precisely for graphs containing $K_{d,\Delta}$. More generally, if $q_B(G)\ge d\Delta-s$, where $0\le s<\Delta$, then $G$ contains $K_{d,\Delta-s}$; if also $s<d$, then $G$ has at least $d-s$ vertices of degree $\Delta$ with the same open neighborhood. For $\Delta\ge3$, we further show that every $K_{3,\Delta}$-free 3-degenerate graph satisfies $q_B(G)\le3\Delta-2$; the example $K_{3,\Delta-1}$ shows that this bound is best possible up to one. For loopless multigraphs, we establish a sharp gap in the possible values of $q_B(G)$. For every integer $\Delta\ge3$, every finite loopless multigraph $G$ with $\Delta(G)\le\Delta$ satisfies $$q_B(G)\le\Delta(\Delta-1)$$ unless $G$ has a component isomorphic to $K_{\Delta,\Delta}$, in which case $q_B(G)=\Delta^2$. The bound $\Delta(\Delta-1)$ is attained by both $K_{\Delta,\Delta-1}$ and $K_{\Delta,\Delta}-e$. Consequently, among finite loopless multigraphs with maximum degree at most $\Delta$, no value of $q_B(G)$ lies strictly between $\Delta^2-\Delta$ and $\Delta^2$.
A $(k,d)$-edge coloring of a loopless multigraph $G$ is an edge coloring using at most $k$ colors such that the subgraph formed by each color class has maximum degree at most $d$. The least such $k$ is denoted by $\chi'_d(G)$. Let $G$ be a loopless non-bipartite multigraph with maximum degree $\Delta(G)$ and odd girth $g_0(G)$, and let $d\ge1$ be odd. We prove that \[ \chi'_d(G)\le\left\lceil\frac{g_0(G)\Delta(G)-1}{dg_0(G)-1}\right\rceil. \] For $d=1$, this is Goldberg's odd-girth refinement of Shannon's theorem, while for $g_0(G)=3$ it is the defective Shannon bound of Aboulker, Aubian, and Huang. For every odd $d>1$, every odd $g_0\ge3$, and every $\Delta>d$, an almost full ring multigraph $R(\Delta,g_0)$, an odd cycle with edge multiplicities alternating between $\lfloor\Delta/2\rfloor$ and $\lceil\Delta/2\rceil$, except that two consecutive edges have multiplicity $\lfloor\Delta/2\rfloor$, attains equality. We also derive a range in which the defective Goldberg--Seymour conjecture holds.
In this paper, we generalize the concept of packing total coloring by introducing a new concept called the $S$-packing total coloring. For a graph $G$ and a non-decreasing sequence $S=(a_1,a_2,\ldots)$ of positive integers, an $S$-packing total coloring of $G$ is a mapping $c: V(G)\cup E(G)\rightarrow \{1,2,\ldots\}$ such that for any two distinct elements $A,B\in V(G)\cup E(G)$ with $c(A)=c(B)=i$, the distance between $A$ and $B$ is at least $a_i+1$. The smallest integer $k$ such that $G$ admits an $S$-packing total coloring using $k$ colors is called the $S$-packing total chromatic number of $G$, denoted by $\chi_S^{''}(G)$. For any sequence $S$, we establish general lower and upper bounds for $\chi_S^{''}(G)$, and characterize all graphs $G$ with $\chi_S^{''}(G)\in\{1,2,3\}$. Furthermore, we investigate $S$-packing total chromatic numbers of complete bipartite graphs, as well as infinite and finite paths and cycles.
Jasmina Ferme, Jaka Hedžet, Petra Melicharová et al.· 0 citations
Gy\'arf\'as and S\'ark\"ozy [Studia Sci. Math. Hungar., 2023] defined a B-coloring of a graph to be a proper coloring of the edge set in which any $C_4$ is totally multicolored. Let $q_B(G)$ denote the minimum number of colors sufficient for a B-coloring of a graph $G$. In this paper, we prove that any planar graph $G$ with $\Delta=\Delta(G)$ and $\Delta_2=\Delta_2(G)$ has $q_B(G)\leq\Delta+\max\{\Delta_2,38\}$, refining a bound by Kong, Wang, and Zheng [J. Graph Theory, 2026].
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 upper bound on $\chi'_D(G)$ is $\frac{9}{16}\Delta^2 + \frac{1}{2}\Delta$, given by a greedy coloring. In this paper, using a probabilistic method, we obtain the first improvement upon this upper bound by proving that $\chi'_D(G) \le (1-c)\frac{9}{16}\Delta^2$ for some $c>0$ and sufficiently large $\Delta$.
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.
