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.
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$.
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 edge colorings of graphs, SIAM J. Discrete Math. 40 (2026) 897--904), which states that $\chi_k'(G)\leq k+o(k)$ for every $0_k$-graph $G$. We prove a lower bound for $0_k$-graphs with degree set $\{k,2k\}$ and a specified vertex partition. With a suitable choice of the part sizes, if the number of edges inside one part is $o(k^2)$, then $\chi_k'(G)\geq(4-2\sqrt2+o(1))k$. This gives connected bipartite and connected nonbipartite counterexamples. In particular, the same examples also disprove the earlier conjecture of Botler, Colucci, and Kohayakawa (The mod $k$ chromatic index of graphs is $O(k)$, J. Graph Theory 102 (2023) 197--200), which states that $\chi_k'(G)\leq k+C$ for some absolute constant $C$.
The adjacent vertex distinguishing (AVD)-total chromatic number $\chi''_{a}(G)$ of a graph $G$ is the least integer $k$ for which $G$ has a proper total coloring $f$ with $k$ colors such that $C_G(u)\neq C_G(v)$ for every edge $uv\in E(G)$, where $C_G(u)=\{f(u)\}\cup\{f(uw):uw\in E(G)\}$. The AVD-total coloring conjecture (AVD-TCC) asserts that $\chi''_{a}(G)\leq \Delta(G)+3$ for every simple graph $G$, where $\Delta(G)$ is the maximum degree of $G$. In this paper, we prove the AVD-TCC for certain classes of graph products, including Cartesian products, lexicographic products, skew products, cover products, comb products, and Indu--Bala products.
A. Banerjee, J. Geetha, Kanagasabapathi Somasundaram· 0 citations
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$.
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.
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$.
