Abstract. Given a graph [Formula: see text] and an integer [Formula: see text], let [Formula: see text] denote the minimum number of colors required to color the edges of [Formula: see text] such that, in each color class, the subgraph induced by the edges of that color has all nonzero degrees congruent to 1 modulo [Formula: see text]. In 1992, Pyber proved that [Formula: see text] for every graph [Formula: see text], and posed the question of whether [Formula: see text] can be bounded solely in terms of [Formula: see text] for every [Formula: see text]. This question was answered in 1997 by Scott, who showed that [Formula: see text], and further asked whether [Formula: see text]. Recently, Botler, Colucci, and Kohayakawa (2023) answered Scott’s question affirmatively proving that [Formula: see text], and conjectured that the multiplicative constant could be reduced to 1. A step towards this latter conjecture was made in 2024 by Nweit and Yang, who improved the bound to [Formula: see text]. In this paper, we further improve the multiplicative constant to 9. More specifically, we prove that there is a function [Formula: see text] for which [Formula: see text] if [Formula: see text] is odd, and [Formula: see text] if [Formula: see text] is even. In doing so, we prove that [Formula: see text] for every [Formula: see text]-degenerate graph [Formula: see text], which plays a central role in our proof.

We say that a sequence a1 . . . a2t of integers is repetitive if ai = ai+t for every i ϵ {1,...,t}. A walk in a graph G is a sequence v1 . . . vr of vertices of G in which vivi+1 ϵ E(G) for every i ϵ {1,..., r - 1}. Given a k-coloring c: V(G) → {1,..., k} of V(G), we say that c is walk-nonrepetitive if for every t ϵ N, for every walk v1 . . . v2t in G the sequence c(V1) . . . c(v2t) is not repetitive unless vi = vi+t for every i ϵ {1,..., t}, and the walk-nonrepetitive chromatic number σ(G) of G is the minimum k for which G has a walk-nonrepetitive k-coloring. Let Cn denote the cycle with n vertices. In this paper we show that σ(Cn) = 4 whenever n ≥ 4 and n ∉ {5,7}, which answers a question posed by Barát and Wood in 2008.

Let Sk(n) be the maximum number of orientations of an n-vertex graph G in which no copy of Kk is strongly connected. For all integers n, k ≥ 4 where n ≥ 5 or k ≥ 5, we prove that Sk(n) = 2tk - 1(n), where tk-1(n) is the number of edges of the n-vertex (k - 1)-partite Turán graph Tk-1(n). Moreover, we prove that Tk-1(n) is the only graph having 2tk-1(n) orientations with no strongly connected copies of Kk.

The 2-Decomposition Conjecture, equivalent to the 3-Decomposition Conjecture stated in 2011 by Hoffmann-Ostenhof, claims that every connected graph G with vertices of degree 2 and 3, and satisfying that G - E(C) is disconnected for every cycle C, admits a decomposition into a spanning tree and a matching. In this work we show that the 2-Decomposition Conjecture holds for graphs whose vertices of degree 3 induce a collection of cacti in which each vertex belongs to a cycle.