betaFeedback

WorksMathematics

On strong odd colorings of sparse graphs

Abstract

A strong odd coloring of a graph is a proper vertex coloring such that for every vertex vv, each color appearing on the neighborhood of vv appears an odd number of times. We investigate strong odd colorings of sparse graphs, where sparsity of a graph GG is measured in terms of maximum average degree, denoted mad⁡(G)\operatorname{mad}(G). We prove that the optimal threshold on the maximum average degree guaranteeing a strong odd cc-coloring is 4−Θ(1c)4-Θ(\frac{1}{c}) as c→∞c\to\infty. Moreover, for every c≥5c\geq 5, this threshold is strictly smaller than the threshold for odd cc-coloring. We also determine the sharp threshold on the maximum average degree guaranteeing a strong odd 55-coloring: every graph GG with mad⁡(G)<73\operatorname{mad}(G)<\frac{7}{3} has a strong odd 55-coloring, and this bound is sharp. In addition, we show that every graph GG with mad⁡(G)<115\operatorname{mad}(G)<\frac{11}{5} and no induced 55-cycle has a strong odd 44-coloring. Note that the 55-cycle has maximum average degree 2 and no strong odd 44-coloring.

Introduction

All graphs in this paper are finite and simple, unless stated otherwise. For a graph GG, let V(G)V(G), E(G)E(G), and Δ(G)\Delta(G) denote its vertex set, edge set, and maximum degree, respectively. The complete graph on nn vertices is denoted by KnK_n. A proper cc-coloring of a graph GG is a function φ:V(G)→{1,…,c}\varphi: V(G) \to\{1,\ldots,c\} that assigns distinct colors to adjacent vertices, and the chromatic number of GG, denoted χ(G)\chi(G), is the minimum cc for which GG has a proper cc-coloring.

Recently introduced by Kwon and Park [7], a strong odd cc-coloring of a graph GG is a proper cc-coloring such that for each vertex vv, every color appearing on its neighborhood NG(v)N_G(v) appears an odd number of times. The strong odd chromatic number of GG, denoted χso(G)\chi_{\mathrm{so}}(G), is the minimum cc for which GG has a strong odd cc-coloring. Note that every graph has a strong odd coloring, as we can give every vertex its own color.

Strong odd coloring lies between two well-studied coloring notions. The first is an odd cc-coloring, introduced by Petr̆uševski and Škrekovski [9], which is a proper cc-coloring such that, for every nonisolated vertex vv, there exists a color appearing an odd number of times on NG(v)N_G(v). The second is a proper coloring of the square of GG, denoted G2G^2, which is the graph obtained from GG by adding edges between vertices at distance 2. For a graph GG, every proper coloring of G2G^2 is a strong odd coloring of GG, since for every vertex vv, the vertices in NG(v)N_G(v) receive pairwise distinct colors. Therefore, χ(G)≤χo(G)≤χso(G)≤χ(G2)\chi(G) \le\chi_o(G) \le\chi_{so}(G) \le\chi(G^2), where χo(G)\chi_o(G) is the minimum cc for which GG has an odd cc-coloring.

Even for a sparse graph GG, strong odd coloring of GG and proper coloring of G2G^2 behave quite differently. Indeed, the closed neighborhood NG(v)∪{v}N_G(v) \cup\{v\} of a vertex in GG becomes a clique in G2G^2, so χ(G2)≥Δ(G)+1\chi(G^2) \ge\Delta(G) + 1. In particular, squares of planar graphs have unbounded chromatic number. In contrast, there exists a minimum constant CsoC_{\mathrm{so}} for which all planar graphs have a strong odd CsoC_{\mathrm{so}}-coloring. Caro et al. [1] proved that Cso≤388C_{\mathrm{so}} \le388, which was recently improved to Cso≤368C_{\mathrm{so}} \le368 by Santra [11]. On the other hand, Cso≥20C_{\mathrm{so}} \ge20, as there is a planar graph with strong odd chromatic number 20 [4, 11]. More generally, Goetze et al. [4] showed that every proper minor-closed class has bounded strong odd chromatic number, and Pilipczuk [10] extended this result to classes of bounded expansion. Nevertheless, the strong odd chromatic number cannot be bounded by a function of the odd chromatic number [4].

In this paper, we study strong odd colorings of sparse graphs, where sparsity is measured in terms of maximum average degree; the maximum average degree of a graph GG, denoted mad⁡(G)\operatorname{mad}(G), is

mad⁡(G)=max⁡∅≠F⊆G2∣E(F)∣∣V(F)∣.\operatorname{mad}(G)=\max_{\varnothing\ne F\subseteq G}\frac{2|E(F)|}{|V(F)|}.

Kwon and Park [7] proved that every graph GG with mad⁡(G)≤207\operatorname{mad}(G) \le\frac{20}{7} satisfies χso(G)≤Δ(G)+4\chi_{\mathrm{so}}(G) \le\Delta(G) + 4, and every graph GG with no 4-cycle and mad⁡(G)≤3011\operatorname{mad}(G) \le\frac{30}{11} satisfies χso(G)≤Δ(G)+3\chi_{\mathrm{so}}(G) \le\Delta(G) + 3. In contrast, we seek conditions on the maximum average degree that guarantee a strong odd cc-coloring for a given number cc of colors.

The corresponding problem for odd coloring is completely resolved for c≥5c \ge5: the exact threshold on the maximum average degree guaranteeing an odd cc-coloring is known [2, 3]. Namely, for c≥5c \ge5, if GG is a graph with mad⁡(G)<4cc+2\operatorname{mad}(G) < \frac{4c}{c+2}, then χo(G)≤c\chi_o(G) \le c. The bound on the density is sharp: the graph S(Kc+1)S(K_{c+1}) obtained by subdividing every edge of Kc+1K_{c+1} exactly once satisfies mad⁡(S(Kc+1))=4cc+2\operatorname{mad}(S(K_{c+1})) = \frac{4c}{c+2} and χo(S(Kc+1))=c+1\chi_o(S(K_{c+1})) = c + 1. Therefore, for every ε>0\varepsilon> 0, the odd chromatic number is bounded on the class of graphs GG with mad⁡(G)<4−ε\operatorname{mad}(G) < 4 - \varepsilon, whereas it is unbounded on the class of graphs GG with mad⁡(G)<4\operatorname{mad}(G) < 4.

Our first main result establishes the analogous phenomenon for strong odd coloring. Namely, for every ε>0\varepsilon> 0, the strong odd chromatic number is bounded on the class of graphs GG with mad⁡(G)<4−ε\operatorname{mad}(G) < 4 - \varepsilon. We also determine the optimal order of this bound as ε→0\varepsilon\to0.

Theorem 1.1. Let c≥54c \ge54 be an integer. For a graph GG, if mad⁡(G)<4−96c−65+(c−65)2+1152\operatorname{mad}(G) < 4 - \frac{96}{c-65+\sqrt{(c-65)^2+1152}}, then χso(G)≤c\chi_{\mathrm{so}}(G) \le c.

Note that the density bound in Theorem 1.1 is 4−48c+O(1c2)4 - \frac{48}{c} + O\left(\frac{1}{c^2}\right). We also construct a family of graphs HcH_c satisfying mad⁡(Hc)=4−8c+O(1c2)\operatorname{mad}(H_c) = 4 - \frac{8}{c} + O\left(\frac{1}{c^2}\right) and χso(Hc)>c\chi_{\mathrm{so}}(H_c) > c. Therefore, the density threshold guaranteeing a strong odd cc-coloring is 4−Θ(1c)4 - \Theta\left(\frac{1}{c}\right) as c→∞c \to\infty. Equivalently, the minimum number of colors required for a strong odd coloring of every graph GG with mad⁡(G)<4−ε\operatorname{mad}(G) < 4 - \varepsilon is Θ(1ε)\Theta\left(\frac{1}{\varepsilon}\right) as ε→0\varepsilon\to0. Moreover, HcH_c satisfies mad⁡(Hc)<4cc+2\operatorname{mad}(H_c) < \frac{4c}{c+2} for every c≥5c \ge5. Thus, χo(Hc)≤c<χso(Hc)\chi_o(H_c) \le c < \chi_{\mathrm{so}}(H_c), so the threshold on the maximum average degree guaranteeing a strong odd cc-coloring is strictly smaller than that for odd cc-coloring.

We next consider strong odd colorings with few colors. For five colors, we obtain the following sharp result.

Theorem 1.2. For a graph GG, if mad⁡(G)<73\operatorname{mad}(G) < \frac{7}{3}, then χso(G)≤5\chi_{\mathrm{so}}(G) \le5.

The bound on the maximum average degree in Theorem 1.2 is sharp as there is a graph Q5Q_5 with mad⁡(Q5)=73\operatorname{mad}(Q_5)=\frac{7}{3} and no strong odd 5-coloring.

For four colors, the 5-cycle has maximum average degree 2 and no strong odd 4-coloring. Nonetheless, excluding induced 5-cycles allows us to obtain a bound greater than 2 on the maximum average degree that guarantees a strong odd 4-coloring.

Theorem 1.3. If a graph GG has no induced 5-cycles and mad⁡(G)<115\operatorname{mad}(G)<\frac{11}{5}, then χso(G)≤4\chi_{\mathrm{so}}(G)\le4.

The graph consisting of two 4-cycles sharing exactly one vertex has no induced 5-cycle, has maximum average degree 167\frac{16}{7}, and has no strong odd 4-coloring.

Our results imply corollaries regarding planar graphs with girth restrictions. Every planar graph with girth at least g≥3g\ge3 has maximum average degree less than 2gg−2\frac{2g}{g-2}. From our results, we obtain the following corollary:

Corollary 1.4. Let GG be a planar graph with girth at least gg.

  • If g≥5g\ge5, then χso(G)≤6⌊12+4g−2+8g−4⌋\chi_{\mathrm{so}}(G)\le6\left\lfloor12+\frac{4}{g-2}+\frac{8}{g-4}\right\rfloor.

  • If g≥14g\ge14, then χso(G)≤5\chi_{\mathrm{so}}(G)\le5.

  • If g≥22g\ge22, then χso(G)≤4\chi_{\mathrm{so}}(G)\le4.

The paper is organized as follows. In § 2, we present the graph Q5Q_5 showing that Theorem 1.2 is sharp and the graph HcH_c related to Theorem 1.1. In § 3, we prove structural lemmas to establish the reducible configurations needed to prove Theorems 1.2 and 1.3, which are completed in § 4 and § 5, respectively, via discharging. In § 6, we prove Theorem 1.1 using a theorem of Lužar, Petruševski, and Škrekovski [8] on odd edge-colorings of loopless multigraphs. Finally, we suggest a potential future research direction in § 7.

We end this section with some notation used throughout the paper. For a graph GG and a vertex vv, let dG(v)d_G(v), NG(v)N_G(v), and NG[v]N_G[v] denote the degree, open neighborhood, and closed neighborhood of vv, respectively. Subscripts are omitted when the graph is clear. A kk-vertex, a k+k^+-vertex, and a k−k^--vertex are vertices of degree kk, at least kk, and at most kk, respectively. A kk-neighbor, a k+k^+-neighbor, and a k−k^--neighbor are neighbors of degree kk, at least kk, and at most kk, respectively.

Extremal examples

In this section, we construct sparse graphs that have no strong odd cc-coloring. Note that a subgraph FF of GG with average degree mad⁡(G)\operatorname{mad}(G) is always an induced subgraph. Moreover, if mad⁡(G)>2\operatorname{mad}(G)>2, then FF must have minimum degree at least 2, otherwise we can remove a vertex of degree at most 1 from FF to increase its average degree.

Five colors

Let Q5Q_5 be the graph obtained by connecting two vertices u,vu,v with three internally vertex-disjoint paths upvupv, uqvuqv, uxyvuxyv. We first show mad⁡(Q5)=73\operatorname{mad}(Q_5)=\frac{7}{3}. Note that the average degree of Q5Q_5 is 73\frac{7}{3}. Let HH be a (induced) subgraph of Q5Q_5 with the maximum average degree; note that HH must have minimum degree at least 2. If HH is a cycle, then mad⁡(H)=2\operatorname{mad}(H)=2. Otherwise, HH is the entire graph Q5Q_5, so mad⁡(H)=73\operatorname{mad}(H)=\frac{7}{3}. Hence mad⁡(Q5)=73\operatorname{mad}(Q_5)=\frac{7}{3}. Now, we prove Q5Q_{5} has no strong odd 5-coloring. Suppose to the contrary that Q5Q_{5} has a strong odd 5-coloring φ\varphi. Every two distinct vertices in {u,x,y,v}\{u,x,y,v\} are either adjacent or the neighborhood of a 2-vertex of Q5Q_{5}. Therefore, all four vertices in {u,x,y,v}\{u,x,y,v\} must receive distinct colors. Since pp is adjacent to uu and vv, φ(p)∉{φ(u),φ(v)}\varphi(p) \notin\{\varphi(u),\varphi(v)\}. If φ(p)=φ(x)\varphi(p)=\varphi(x), then, since N(u)={p,q,x}N(u)=\{p,q,x\}, φ(q)\varphi(q) must be the same as φ(x)\varphi(x), so φ(x)\varphi(x) appears exactly twice on N(v)N(v), which is a contradiction. Thus φ(p)≠φ(x)\varphi(p)\ne\varphi(x). Similarly, φ(p)≠φ(y)\varphi(p)\ne\varphi(y). Hence, φ(p)\varphi(p) does not appear on {u,v,x,y}\{u,v,x,y\}. By symmetry, φ(q)\varphi(q) also does not appear on {u,v,x,y}\{u,v,x,y\}. Then φ(p)=φ(q)\varphi(p)=\varphi(q), which is a contradiction since now φ(p)\varphi(p) appears exactly twice on N(u)N(u). Therefore Q5Q_{5} has no strong odd 5-coloring.

A general construction

Given a graph FF, let S(F)S(F) denote the graph obtained from FF by subdividing each edge exactly once; the branch vertices are the vertices that existed before the subdivision. For an integer c≥4c\ge4, set a=⌊c2⌋a=\left\lfloor\frac{c}{2}\right\rfloor, b=⌈c2⌉b=\left\lceil\frac{c}{2}\right\rceil, and Tc=a2+b2=⌈c22⌉T_{c}=a^{2}+b^{2}=\left\lceil\frac{c^{2}}{2}\right\rceil. We define the graph HcH_{c} from the disjoint union of S(Ka)S(K_{a}) and S(Kb)S(K_{b}) by adding a vertex zz adjacent to all cc branch vertices. Note that HcH_{c} has a+(a2)+b+(b2)+1=a2+a+b2+b+22=Tc+c+22a+\binom{a}{2}+b+\binom{b}{2}+1=\frac{a^{2}+a+b^{2}+b+2}{2}=\frac{T_{c}+c+2}{2} vertices and 2(a2)+2(b2)+a+b=a2+b2=Tc2\binom{a}{2}+2\binom{b}{2}+a+b=a^{2}+b^{2}=T_{c} edges.

We first show HcH_{c} has no strong odd cc-coloring. Suppose to the contrary that HcH_{c} has a strong odd cc-coloring φ\varphi. All neighbors of zz are branch vertices from S(Ka)S(K_{a}) and S(Kb)S(K_{b}). Two branch vertices u,vu,v from the same copy of S(Kr)S(K_{r}) for some r∈{a,b}r\in\{a,b\} form the neighborhood of a 2-vertex, so u,vu,v must receive distinct colors. Therefore if two branch vertices receive the same color, then the color appears exactly twice on N(z)N(z), which is a contradiction. Thus all cc vertices in N(z)N(z) receive pairwise distinct colors. Now, there is no color for zz, which is a contradiction. Hence, HcH_{c} has no strong odd cc-coloring.

We show that mad⁡(Hc)=4TcTc+c+2=4−8(c+2)c2+2c+4+ε\operatorname{mad}(H_{c})=\frac{4T_{c}}{T_{c}+c+2}=4-\frac{8(c+2)}{c^{2}+2c+4+\varepsilon} where ε∈{0,1}\varepsilon\in\{0,1\} and ε≡c(mod2)\varepsilon\equiv c\pmod2. Note that the graph HcH_{c} has average degree 4TcTc+c+2>2\frac{4T_{c}}{T_{c}+c+2}>2. Let FF be a (induced) subgraph of HcH_{c} with maximum average degree; note that FF must have minimum degree at least 2. Suppose FF has pp and qq branch vertices from S(Ka)S(K_{a}) and S(Kb)S(K_{b}), respectively. Since FF has minimum degree at least 2, we have p+q≥2p+q\ge2. The graph HcH_{c} is 2-degenerate, so every subgraph of HcH_{c} has average degree less than 4. Thus, adding zz to FF does not decrease its average degree, so we may assume that FF contains zz. Moreover, whenever FF contains two branch vertices u,vu,v from the same copy of S(Kr)S(K_{r}) for some r∈{a,b}r\in\{a,b\}, adding the u,vu,v-path of length 2 to FF does not decrease its average degree. Therefore we may assume that FF has p2+q2p^{2}+q^{2} edges and p2+q2+p+q+22\frac{p^{2}+q^{2}+p+q+2}{2} vertices. Hence the average degree of FF is mad⁡(Hc)=g(p,q)=4(p2+q2)p2+q2+p+q+2\operatorname{mad}(H_{c})=g(p,q)=\frac{4(p^{2}+q^{2})}{p^{2}+q^{2}+p+q+2} where 0≤p≤a0\le p\le a and 0≤q≤b0\le q\le b. Maximizing g(p,q)g(p,q) is equivalent to maximizing f(p,q)=p2+q2p+q+2f(p,q)=\frac{p^{2}+q^{2}}{p+q+2}, since g(p,q)=4f(p,q)f(p,q)+1g(p,q)=\frac{4f(p,q)}{f(p,q)+1} and the function 4x/(x+1)4x/(x+1) is strictly increasing for x≥0x\ge0. For fixed q≥0q\ge0, the function f(p,q)f(p,q) is strictly convex in pp, since ∂2f∂p2=4(q2+2q+2)(p+q+2)3>0\frac{\partial^{2}f}{\partial p^{2}}=\frac{4(q^{2}+2q+2)}{(p+q+2)^{3}}>0. By symmetry, ff is strictly convex in each variable, so every maximizer in [0,a]×[0,b][0,a]\times[0,b] must lie at a corner. Since b≥ab\ge a, we have f(0,0)<f(a,0)≤f(0,b)f(0,0)<f(a,0)\le f(0,b). Moreover, f(a,b)−f(0,b)=a(a(b+2)−b2)(a+b+2)(b+2)>0f(a,b)-f(0,b)=\frac{a(a(b+2)-b^{2})}{(a+b+2)(b+2)}>0 since b∈{a,a+1}b\in\{a,a+1\} and a≥2a\ge2 imply a(b+2)−b2≥a−1>0a(b+2)-b^{2}\ge a-1>0. Thus ff is maximized at a unique point (a,b)(a,b), so F=HcF=H_{c}.

Reducible configurations

Fix an integer c≥3c\ge3. A graph GG is strong odd cc-minimal if GG has no strong odd cc-coloring but every proper subgraph of GG has a strong odd cc-coloring. In this section, we identify several reducible configurations that cannot occur in a strong odd cc-minimal graph GcG_c. By minimality, GcG_c is connected. We will use the color set Cc\mathcal{C}_c of cc colors; in particular, {α,β,γ,δ}⊆Cc\{\alpha,\beta,\gamma,\delta\} \subseteq\mathcal{C}_c when c≥4c \ge4.

An open tt-thread is a path between distinct vertices x,yx,y with exactly tt internal vertices, which are all 2-vertices; x,yx,y are its terminals. A closed tt-thread is a cycle with exactly one 3+3^{+}-vertex and tt 2-vertices; the 3+3^{+}-vertex is its terminal. A thread is maximal if it is not properly contained in a longer thread. We say that a terminal is incident with the thread. For a positive integer ss, an s+s^{+}-thread is a tt-thread where t≥st \ge s.

A 2-vertex vv is nearby a 3+3^{+}-vertex uu if vv lies on a thread incident with uu. A 3+3^{+}-vertex uu is responsible for rr nearby 2-vertices if the total number of nearby 2-vertices of uu, counted with multiplicity, is rr, where a nearby 2-vertex on a maximal open and closed thread incident with uu is counted once and twice, respectively.

Common configurations

Lemma 3.1. If c≥3c \ge3, then GcG_c satisfies the following:

(i) Every vertex has at most one 1-neighbor.

(ii) If a vertex uu has a 1-neighbor, then d(u)≥cd(u) \ge c and d(u)≡c(mod2)d(u) \equiv c \pmod{2}. In particular, a 1-vertex has a c+c^{+}-neighbor, and no (c+1)(c+1)-vertex has a 1-neighbor.

Proof. (i): Suppose to the contrary that a vertex uu has two 1-neighbors xx and yy. Let φ\varphi be a strong odd cc-coloring of Gc−{x,y}G_c-\{x,y\}. If uu has no neighbors in Gc−{x,y}G_c-\{x,y\}, then GcG_c is a path on three vertices, which has a strong odd 3-coloring. Otherwise, uu has a neighbor zz distinct from x,yx,y, so color both xx and yy with φ(z)\varphi(z). In either case, we obtain a strong odd cc-coloring of GcG_c, which is a contradiction.

(ii): Suppose that a vertex uu has a 1-neighbor xx. Let φ\varphi be a strong odd cc-coloring of Gc−xG_c-x. If a color α\alpha does not appear in φ(N[u]∖{x})\varphi(N[u]\setminus\{x\}), then let φ(x)=α\varphi(x)=\alpha to obtain a strong odd cc-coloring of GcG_c, which is a contradiction. Otherwise, all cc colors appear in φ(N[u]∖{x})\varphi(N[u]\setminus\{x\}), so d(u)≥cd(u) \ge c. Moreover, every color distinct from φ(u)\varphi(u) appears on N(u)∖{x}N(u)\setminus\{x\} an odd number of times, so d(u)=1+∑α∈Cc∖{φ(u)}∣(N(u)∖{x})∩φ−1(α)∣≡1+(c−1)(mod2).d(u)=1+\sum_{\alpha\in\mathcal{C}_c\setminus\{\varphi(u)\}} |(N(u)\setminus\{x\})\cap\varphi^{-1}(\alpha)| \equiv1+(c-1)\pmod{2}.

Lemma 3.2. Let c≥4c \ge4. If a vertex uu of GcG_c is incident with a closed tt-thread, then t∈{2,3}t \in\{2,3\} and uu is a c+c^{+}-vertex. Moreover, if uu has a 1-neighbor, then uu is a (c+2)+(c+2)^{+}-vertex.

Proof. Let T=ux1x2…xtuT=ux_1x_2\ldots x_tu be a closed tt-thread. Let φ\varphi be a strong odd cc-coloring of Gc−{x1,…,xt}G_c-\{x_1,\ldots,x_t\}. Since uu is a 3+3^{+}-vertex, uu has a neighbor ww not on TT. Let α=φ(u)\alpha=\varphi(u) and β=φ(w)\beta=\varphi(w). Suppose to the contrary that t≥4t\ge4. Extend φ\varphi to x1,xtx_1,x_t by coloring x1,xtx_1,x_t with β\beta. Now, we can easily extend this coloring to a strong odd cc-coloring of GcG_c, a contradiction. Therefore t∈{2,3}t\in\{2,3\}. Suppose to the contrary that d(u)≤c−1d(u)\le c-1. Since ∣N[u]∖{x1,xt}∣=d(u)−1≤c−2|N[u]\setminus\{x_1,x_t\}|=d(u)-1\le c-2, there are distinct colors γ,δ∉φ(N[u]∖{x1,xt})\gamma,\delta\notin\varphi(N[u]\setminus\{x_1,x_t\}). Extend φ\varphi to x1,xtx_1,x_t by coloring x1,xtx_1,x_t with γ,δ\gamma,\delta, respectively. If t=2t=2, then we color x2x_2 with the color of GcG_c. Otherwise t=3t=3, so color the only uncolored vertex x2x_2 with β\beta. In either case, we obtain a strong odd cc-coloring of GcG_c, which is a contradiction.

For the moreover part, suppose to the contrary that uu is a (c+1)−(c+1)^{-}-vertex with a 1-neighbor zz. Since uu is a c+c^{+}-vertex and c≥4c\ge4, uu has a neighbor w∉{z,x1,xt}w\notin\{z,x_1,x_t\}. Let ψ\psi be a strong odd cc-coloring of Gc−{z,x1,…,xt}G_c-\{z,x_1,\ldots,x_t\}. Let α=ψ(u)\alpha=\psi(u) and β=ψ(w)\beta=\psi(w). Since ∣N[u]∖{z,x1,xt}∣=d(u)−2≤c−1|N[u]\setminus\{z,x_1,x_t\}|=d(u)-2\le c-1, there is a color γ∉ψ(N[u]∖{z,x1,xt})\gamma\notin\psi(N[u]\setminus\{z,x_1,x_t\}). In particular, γ∉{α,β}\gamma\notin\{\alpha,\beta\}. Extend ψ\psi to z,x1,xtz,x_1,x_t by coloring xtx_t with γ\gamma and both zz and x1x_1 with β\beta. If t=2t=2, then we colored all of GcG_c. Otherwise t=3t=3, so color the only uncolored vertex x2x_2 with a color not in {α,β,γ}\{\alpha,\beta,\gamma\}. In either case, we obtain a strong odd cc-coloring of GcG_c, which is a contradiction.

Four colors

Lemma 3.3. Let ux1…xtvux_1\ldots x_tv be an open tt-thread of G4G_4 with t≥2t \ge2 and let HH be an induced subgraph of G4−{x1,…,xt−1}G_4-\{x_1,\ldots,x_{t-1}\} where u,xt,v∈V(H)u,x_t,v \in V(H). Suppose that φ\varphi is a proper 4-coloring of HH where the strong odd condition is not violated at any vertex of HH, except possibly at uu. If either t=2t=2 and φ(u)≠φ(x2)\varphi(u) \ne\varphi(x_2) or t≥3t \ge3, then φ\varphi can be extended to x1,…,xt−1x_1,\ldots,x_{t-1} so that the resulting coloring is proper and the strong odd condition is not violated at any vertex of G4[V(H)∪{x1,…,xt−1}]G_4[V(H) \cup\{x_1,\ldots,x_{t-1}\}], except possibly at uu. Moreover, if either t=3t=3 and φ(u)=φ(x3)\varphi(u)=\varphi(x_3) or t=4t=4 and φ(u)≠φ(v)\varphi(u) \ne\varphi(v), then x1x_1 may be assigned any color other than φ(u)\varphi(u) in such an extension.

Proof. If t=2t=2 and φ(u)≠φ(x2)\varphi(u) \ne\varphi(x_2), then color x1x_1 with a color not in φ({u,x2,v})\varphi(\{u,x_2,v\}). Suppose t≥3t \ge3. Sequentially, for each ii from t−1t-1 to 2, color xix_i with a color not appearing on vertices within distance 2; xi−1x_{i-1} is not colored yet, so there are at most three colors to avoid. Finally, color x1x_1 with a color not in φ({u,x2,x3})\varphi(\{u,x_2,x_3\}).

We now prove the moreover part. Assign a color other than φ(u)\varphi(u) for x1x_1. If t=3t=3 and φ(u)=φ(x3)\varphi(u)=\varphi(x_3), then color x2x_2 with a color not in φ({u,x1,v})\varphi(\{u,x_1,v\}). Assume t=4t=4 and φ(u)≠φ(v)\varphi(u) \ne\varphi(v). If φ(x4)≠φ(u)\varphi(x_4) \ne\varphi(u), then color x3x_3 with φ(u)\varphi(u) and color x2x_2 with a color not in φ({u,x1,x4})\varphi(\{u,x_1,x_4\}). Otherwise, φ(x4)=φ(u)\varphi(x_4)=\varphi(u), so color x3x_3 with a color not in φ({u,x1,v})\varphi(\{u,x_1,v\}) and color x2x_2 with a color not in φ({u,x1,x3})\varphi(\{u,x_1,x_3\}).

Lemma 3.4. G4G_4 satisfies the following:

  1. There is no open 6+6^+-thread.

  2. A 3-vertex is not incident with two internally disjoint open 5+5^+-threads.

  3. A 4-vertex with a 1-neighbor is not incident with an open 5+5^+-thread.

Proof. (i): Suppose to the contrary that ux1…x6vux_1\ldots x_6v is an open 6-thread of G4G_4. Let φ\varphi be a strong odd 4-coloring of G4−{x2,x3,x4}G_4-\{x_2,x_3,x_4\}. We may assume that φ(u)≠φ(x5)\varphi(u) \ne\varphi(x_5); otherwise, recolor x5x_5 with a color not in φ({u,x6,v})\varphi(\{u,x_6,v\}). Then color x4x_4 with a color not in φ({x5,x6})\varphi(\{x_5,x_6\}). By the moreover part of Lemma 3.3, we can extend φ\varphi to a strong odd 4-coloring of G4G_4, which is a contradiction.

(ii): Suppose to the contrary that a 3-vertex uu is incident with two open 5+5^+-threads ux11…x51v1ux_1^1\ldots x_5^1v^1 and ux12…x52v2ux_1^2\ldots x_5^2v^2. Let ww be the neighbor of uu distinct from x11,x12x_1^1,x_1^2. Let φ\varphi be a strong odd 4-coloring of G4−{x11,x21,x31,x41,x12,x22,x32,x42}G_4-\{x_1^1,x_2^1,x_3^1,x_4^1,x_1^2,x_2^2,x_3^2,x_4^2\}. Let α,β\alpha,\beta be distinct colors not in {φ(u),φ(w)}\{\varphi(u),\varphi(w)\}. If {φ(v1),φ(v2)}⊆{α,β}\{\varphi(v^1),\varphi(v^2)\} \subseteq\{\alpha,\beta\}, then color both x11,x12x_1^1,x_1^2 with φ(w)\varphi(w). Otherwise, extend φ\varphi to x11,x12x_1^1,x_1^2 by coloring x11,x12x_1^1,x_1^2 with α,β\alpha,\beta or β,α\beta,\alpha, respectively, so that φ(x11)≠φ(v1)\varphi(x_1^1) \ne\varphi(v^1) and φ(x12)≠φ(v2)\varphi(x_1^2) \ne\varphi(v^2). In either case, for each i∈{1,2}i \in\{1,2\}, color x2ix_2^i with a color not in φ({u,x1i})\varphi(\{u,x_1^i\}). By the moreover part of Lemma 3.3, we can extend φ\varphi to a strong odd 4-coloring of G4G_4, which is a contradiction.

(iii): Suppose to the contrary that a 4-vertex uu has a 1-neighbor ww and is incident with an open 5+5^+-thread ux1…x5vux_1\ldots x_5v. Let y,zy,z be the neighbors of uu distinct from w,x1w,x_1. Let φ\varphi be a strong odd 4-coloring of G4−{w,x1,x2,x3,x4}G_4-\{w,x_1,x_2,x_3,x_4\}. Then φ(u),φ(y),φ(z)\varphi(u),\varphi(y),\varphi(z) are pairwise distinct. Color both w,x1w,x_1 with a color in {φ(y),φ(z)}∖{φ(u)}\{\varphi(y),\varphi(z)\}\setminus\{\varphi(u)\}. Choose a color for x2x_2 not in φ({u,x1})\varphi(\{u,x_1\}). By the moreover part of Lemma 3.3, we can extend φ\varphi to a strong odd 4-coloring of G4G_4, a contradiction.

:::

Lemma 3.5. Let uu be a vertex of G4G_4. If d(u)=4d(u)=4 and uu has a 1-neighbor or d(u)=3d(u)=3, then uu cannot be incident with three pairwise internally disjoint open tit_i-threads where (t1,t2,t3)∈{(1,3,4),(2,2,4),(3,3,3)}(t_1,t_2,t_3)\in\{(1,3,4),(2,2,4),(3,3,3)\}.

Proof. Suppose to the contrary that uu is incident with three pairwise internally disjoint open threads ux1i…xtiiviux_1^i\ldots x_{t_i}^iv^i for i∈{1,2,3}i\in\{1,2,3\} for some (t1,t2,t3)∈{(1,3,4),(2,2,4),(3,3,3)}(t_1,t_2,t_3)\in\{(1,3,4),(2,2,4),(3,3,3)\}. Let X={u,w}X=\{u,w\} if uu is a 4-vertex with a 1-neighbor ww, and let X={u}X=\{u\} otherwise. Let φ\varphi be a strong odd 4-coloring of G4−(X∪{xji:1≤i≤3, 1≤j<ti})G_4-\left(X\cup\{x_j^i:1\leq i\leq3,\ 1\leq j<t_i\}\right). We first color uu with a color α\alpha where

  • α∈C4∖φ({xt11,v1,v3})\alpha\in C_4\setminus\varphi(\{x_{t_1}^1,v^1,v^3\}) if (t1,t2,t3)=(1,3,4)(t_1,t_2,t_3)=(1,3,4),

  • α∈C4∖φ({xt11,xt22,v3})\alpha\in C_4\setminus\varphi(\{x_{t_1}^1,x_{t_2}^2,v^3\}) if (t1,t2,t3)=(2,2,4)(t_1,t_2,t_3)=(2,2,4),

  • α=φ(xt33)\alpha=\varphi(x_{t_3}^3) if (t1,t2,t3)=(3,3,3)(t_1,t_2,t_3)=(3,3,3).

By Lemma 3.3, we can extend φ\varphi to x11,…,xt11,x12,…,xt22x_1^1,\ldots,x_{t_1}^1,x_1^2,\ldots,x_{t_2}^2. We now show how to choose a color (that is not α\alpha) for x13x_1^3 to guarantee that the strong odd condition holds at uu. Let p=φ(x11)p=\varphi(x_1^1) and q=φ(x12)q=\varphi(x_1^2). If d(u)=3d(u)=3, then color x13x_1^3 with pp if p=qp=q and with a color not in {α,p,q}\{\alpha,p,q\} otherwise. If d(u)=4d(u)=4 (so uu has a 1-neighbor ww), then color x13x_1^3 with pp, and color ww with pp if p≠qp\ne q and with a color not in {α,p}\{\alpha,p\} otherwise. Thus, the strong odd condition holds at uu. By the moreover part of Lemma 3.3, any color that is not α\alpha on x13x_1^3 can be extended to complete a strong odd 4-coloring of G4G_4, a contradiction. □

Lemma 3.6. Every 4-vertex of G4G_4 is responsible for at most 18 nearby 2-vertices.

Proof. Suppose to the contrary that G4G_4 has a 4-vertex uu that is responsible for more than 18 nearby 2-vertices. By Lemma 3.2, uu is not incident with a closed 4+4^+-thread. By Lemma 3.4(i), there is no open 6+6^+-thread. Thus, uu must be incident with at least three distinct open 5-threads ux1i…x5iviux_1^i\ldots x_5^iv^i where i∈{1,2,3}i\in\{1,2,3\}. Let ww be the neighbor of uu distinct from x11,x12,x13x_1^1,x_1^2,x_1^3. Let φ\varphi be a strong odd 4-coloring of G4−{xji:1≤i≤3, 1≤j≤4}G_4-\{x_j^i:1\leq i\leq3,\ 1\leq j\leq4\}. Take distinct colors α,β\alpha,\beta not in φ({u,w})\varphi(\{u,w\}). If α∉φ({v1,v2,v3})\alpha\notin\varphi(\{v^1,v^2,v^3\}), then extend φ\varphi by coloring x1ix_1^i with α\alpha for all ii. Otherwise, we may assume φ(v1)=α\varphi(v^1)=\alpha. By the same argument, we may assume φ(v2)=β\varphi(v^2)=\beta. Now, extend φ\varphi by coloring both x11,x12x_1^1,x_1^2 with φ(w)\varphi(w) and x13x_1^3 with a color in {α,β}∖{φ(v3)}\{\alpha,\beta\}\setminus\{\varphi(v^3)\}. Thus, the strong odd condition holds at uu. For each i∈{1,2,3}i\in\{1,2,3\}, choose a color for x2ix_2^i not in φ({u,x1i})\varphi(\{u,x_1^i\}). By the moreover part of Lemma 3.3, we can extend φ\varphi to a strong odd 4-coloring of G4G_4, which is a contradiction. □

Lemma 3.7. Let u,vu,v be adjacent vertices of G4G_4. Suppose that each of u,vu,v is either a 4-vertex with a 1-neighbor or a 3-vertex. Then either G4G_4 contains a 5-cycle or uu and vv cannot both be incident with two internally disjoint open 3+3^+- and 4+4^+-threads.

Proof. Assume that G4G_4 has no 5-cycle. Suppose to the contrary that each of u,vu,v is incident with two internally disjoint open 3+3^+- and 4+4^+-threads. By Lemma 3.2, neither uu nor vv is incident with a closed thread. For each t∈{3,4}t\in\{3,4\}, let Pt=ux1t…xpttxtP^t=ux_1^t\ldots x_{p_t}^tx^t and Qt=vy1t…yqttytQ^t=vy_1^t\ldots y_{q_t}^ty^t be the corresponding maximal threads incident with uu and vv, respectively, where pt,qt≥tp_t,q_t\geq t. For convenience, let xpt+1t+1=xtx_{p_{t+1}}^{t+1}=x^t and yqt+1t+1=yty_{q_{t+1}}^{t+1}=y^t. We call a thread among P3,P4,Q3,Q4P^3,P^4,Q^3,Q^4 shared if its terminals are uu and vv.

First, suppose that there is a shared thread T=uz1…zsvT=uz_1\ldots z_sv. Since uv∈E(G4)uv\in E(G_4) and G4G_4 has no 5-cycle, s≠3s\ne3. Thus s∈{4,5}s\in\{4,5\} by Lemma 3.4(i). Obtain G′G' from G4G_4 by deleting all internal vertices of TT and the 1-neighbors of u,vu,v, if any. Let φ\varphi be a strong odd 4-coloring of G′G'. Let u′u' and v′v' be the neighbors of uu and vv in G′G' other than vv and uu, respectively. Since dG′(u)=dG′(v)=2d_{G'}(u)=d_{G'}(v)=2, the colors on each of {u,v,u′}\{u,v,u'\} and {u,v,v′}\{u,v,v'\} are pairwise distinct. If d(u)=3d(u)=3, then color z1z_1 with a color not in φ({u,v,u′})\varphi(\{u,v,u'\}). Otherwise, d(u)=4d(u)=4, so color both z1z_1 and the 1-neighbor of uu with φ(u′)\varphi(u'). Similarly, color zsz_s and the 1-neighbor of vv, if any. Then the strong odd condition holds at uu, vv, and φ(z1),φ(zs)∉{φ(u),φ(v)}\varphi(z_1),\varphi(z_s)\notin\{\varphi(u),\varphi(v)\}. Color zs−1z_{s-1} with φ(u)\varphi(u). Since φ(u)≠φ(v)\varphi(u)\ne\varphi(v), the strong odd condition holds at zsz_s. Since φ(zs−1)=φ(u)≠φ(zs)\varphi(z_{s-1})=\varphi(u)\ne\varphi(z_s) and s∈{4,5}s\in\{4,5\}, by the moreover part of Lemma 3.3, we can extend φ\varphi to a strong odd 4-coloring of G4G_4, a contradiction.

Now, suppose that there is no shared thread. Obtain G′G' from G4G_4 by deleting u,vu,v, their 1-neighbors, if any, and the vertices x1t,…,xt−1t,y1t,…,yt−1tx_1^t,\ldots,x_{t-1}^t,y_1^t,\ldots,y_{t-1}^t for each t∈{3,4}t\in\{3,4\}. Let φ\varphi be a strong odd 4-coloring of G′G'. Color uu with a color α≠φ(x45)\alpha\ne\varphi(x_4^5). By Lemma 3.3, extend φ\varphi to x23,x13x_2^3,x_1^3, and let γ=φ(x13)\gamma=\varphi(x_1^3). Color vv with a color β∉{α,γ,φ(y45)}\beta\notin\{\alpha,\gamma,\varphi(y_4^5)\}. If d(u)=3d(u)=3, then color x14x_1^4 with a color not in {α,β,γ}\{\alpha,\beta,\gamma\}. Otherwise, d(u)=4d(u)=4, so color both x14x_1^4 and the 1-neighbor of uu with γ\gamma. In either case, the strong odd condition holds at uu. By the moreover part of Lemma 3.3, we can extend φ\varphi to x24,x34x_2^4,x_3^4. By Lemma 3.3, extend φ\varphi to y23,y13y_2^3,y_1^3. If d(v)=3d(v)=3, then color y14y_1^4 with α\alpha when φ(y13)=α\varphi(y_1^3)=\alpha, and with a color not in {α,β,φ(y13)}\{\alpha,\beta,\varphi(y_1^3)\} when φ(y13)≠α\varphi(y_1^3)\ne\alpha. Otherwise, color y14y_1^4 with α\alpha, and color the 1-neighbor of vv with α\alpha when φ(y13)≠α\varphi(y_1^3)\ne\alpha, and with a color not in {α,β}\{\alpha,\beta\} when φ(y13)=α\varphi(y_1^3)=\alpha. In either case, the strong odd condition holds at vv. By the moreover part of Lemma 3.3, we can extend φ\varphi to y24,y34y_2^4,y_3^4. Thus φ\varphi extends to a strong odd 4-coloring of G4G_4, which is a contradiction.

Five colors

The results in this subsection will be used for c=5c=5, but we state and prove them for all c≥5c\ge5.

Lemma 3.8. Let c≥5c\ge5. Both terminals of every open 3-thread of GcG_c are (c−1)+(c-1)^+-vertices. In particular, there is no 4+4^+-thread in GcG_c.

Proof. Suppose to the contrary that there exists a 3-thread ux1x2x3vux_1x_2x_3v with d(u)≤c−2d(u)\le c-2. Let φ\varphi be a strong odd cc-coloring of Gc−{x1,x2}G_c-\{x_1,x_2\}. Since ∣(N[u]∖{x1})∪{x3}∣≤d(u)+1≤c−1\lvert(N[u]\setminus\{x_1\})\cup\{x_3\}\rvert\le d(u)+1\le c-1, there is a color α∉φ(N[u]∖{x1})∪{φ(x3)}\alpha\notin\varphi(N[u]\setminus\{x_1\})\cup\{\varphi(x_3)\}. Since c≥5c\ge5, there is a color β∉φ({u,x3,v})∪{α}\beta\notin\varphi(\{u,x_3,v\})\cup\{\alpha\}. Color x1,x2x_1,x_2 with α,β\alpha,\beta, respectively, to obtain a strong odd cc-coloring of GcG_c, a contradiction.

Lemma 3.9. Let c≥5c\ge5. Suppose two neighbors x11,x12x_1^1,x_1^2 of a vertex uu of GcG_c are on two open 2-threads ux11x21v1ux_1^1x_2^1v^1 and ux12x22v2ux_1^2x_2^2v^2. If x11x_1^1 is not on a closed thread, then at least one of v1,v2v^1,v^2 is a (c−2)+(c-2)^+-vertex. In particular, every vertex is incident with at most one open 3-thread.

Proof. Suppose to the contrary that both v1v^1 and v2v^2 are (c−3)−(c-3)^--vertices. Let φ\varphi be a strong odd cc-coloring of Gc−{x11,x21,x12,x22}G_c-\{x_1^1,x_2^1,x_1^2,x_2^2\}. Let X=φ(N(u)∖{x11,x12})X=\varphi(N(u)\setminus\{x_1^1,x_1^2\}). If some α∈X\alpha\in X is not in {φ(v1),φ(v2)}\{\varphi(v^1),\varphi(v^2)\}, then color x11,x12x_1^1,x_1^2 with α\alpha. Otherwise X⊆{φ(v1),φ(v2)}X\subseteq\{\varphi(v^1),\varphi(v^2)\}, so X∪φ({u,v1,v2})X\cup\varphi(\{u,v^1,v^2\}) has size at most 3. We color x11,x12x_1^1,x_1^2 with distinct colors α,β∉X∪φ({u,v1,v2})\alpha,\beta\notin X\cup\varphi(\{u,v^1,v^2\}), respectively. In either case, the strong odd condition holds at uu. For each i∈{1,2}i\in\{1,2\}, sequentially color x2ix_2^i with a color not appearing on {u,x1i}∪(N[vi]∖{x2i})\{u,x_1^i\}\cup(N[v^i]\setminus\{x_2^i\}), which has size at most d(vi)+2≤c−1d(v^i)+2\le c-1. This is a strong odd cc-coloring of GcG_c, which is a contradiction.

Lemma 3.10. Let c≥5c\ge5. If d∈{3,…,c−2}d\in\{3,\ldots,c-2\}, then the neighbors of a dd-vertex of GcG_c are not on d−1d-1 open 2+2^+-threads and an open 1+1^+-thread.

Proof. Suppose to the contrary that the neighbors of a dd-vertex uu are on d−1d-1 open 2-threads uxiyiviux_iy_iv_i for i∈{1,…,d−1}i\in\{1,\ldots,d-1\} and an open 1-thread uxdvdux_dv_d. Let φ\varphi be a strong odd cc-coloring of Gc−{u,x1,…,xd−1}G_c-\{u,x_1,\ldots,x_{d-1}\}. Since c>d+1c>d+1, we can extend φ\varphi to uu by coloring uu with a color not in φ({xd,vd,y1,…,yd−1})\varphi(\{x_d,v_d,y_1,\ldots,y_{d-1}\}). For i∈{1,…,d−1}i \in\{1,\ldots,d-1\}, let Ai=Cc∖φ({u,yi,vi,xd})A_i=C_c\setminus\varphi(\{u,y_i,v_i,x_d\}), so ∣Ai∣≥c−4≥d−2|A_i|\ge c-4\ge d-2. If A1,…,Ad−1A_1,\ldots,A_{d-1} have distinct representatives (α1,…,αd−1)∈A1×⋯×Ad−1(\alpha_1,\ldots,\alpha_{d-1})\in A_1\times\cdots\times A_{d-1}, then color xix_i with αi\alpha_i for each i∈{1,…,d−1}i\in\{1,\ldots,d-1\}. Otherwise, Hall’s theorem implies that all sets AiA_i are the same set with d−2d-2 elements. This further implies φ(xd)∈Cc∖φ({u,yi,vi})\varphi(x_d)\in C_c\setminus\varphi(\{u,y_i,v_i\}) for every ii. Thus color x1,x2x_1,x_2 with φ(xd)\varphi(x_d) and color x3,…,xd−1x_3,\ldots,x_{d-1} with distinct colors from A1A_1. In either case, φ\varphi extends to a strong odd cc-coloring of GcG_c, which is a contradiction.

Five colors for sparse graphs

In this section, we prove Theorem 1.2. We begin by summarizing the useful reducible configurations for a strong odd 5-minimal graph from § 3.

Corollary 4.1. A strong odd 5-minimal graph satisfies the following:

(i) Every vertex has at most one 1-neighbor, and the neighbor of a 1-vertex has odd degree at least 5.

(ii) The terminal of a closed thread is a 5+5^{+}-vertex. Moreover, a 5-vertex with a 1-neighbor is not incident with a closed thread.

(iii) There is no 4+4^{+}-thread.

(iv) Both terminals of a 3-thread are 4+4^{+}-vertices. In particular, a 3-vertex is not incident with a 3-thread.

(v) Every vertex is incident with at most one open 3-thread.

(vi) The neighbors of a 3-vertex are not on two open 2-threads and an open 1-thread.

Proof. (i) and (ii) follow from Lemma 3.1 and Lemma 3.2, respectively. (iii) and (iv) follow from Lemma 3.8. (v) and (vi) follow from Lemma 3.9 and Lemma 3.10, respectively.

Now, suppose to the contrary that there exists a graph GG with mad⁡(G)<73\operatorname{mad}(G)<\frac{7}{3} that has no strong odd 5-coloring. Choose a strong odd 5-minimal subgraph G′G' of GG. Then G′G' is connected and mad⁡(G′)<73\operatorname{mad}(G')<\frac{7}{3}. Moreover, G′G' is not a cycle, since every cycle has a strong odd 5-coloring.

Let XX be the set of 1-vertices of G′G', and let H=G′−XH=G'-X. By Corollary 4.1(i), each vertex in XX has a 5+5^{+}-neighbor, so HH has minimum degree at least 2 and the 2-vertices of HH are exactly the 2-vertices of G′G'. Every 3+3^{+}-vertex of G′G' remains a 3+3^{+}-vertex in HH, so the maximal threads containing 2-vertices are unchanged. In particular, every 2-vertex of HH lies on a maximal thread with 3+3^{+}-terminals in HH.

We obtain our final contradiction via discharging. To each vertex vv of HH, assign an initial charge of dH(v)d_H(v) and let μ(v)\mu(v) denote its final charge after applying the discharging rule. Since the discharging procedure preserves the total charge, we obtain ∑v∈V(H)μ(v)=∑v∈V(H)dH(v)=2∣E(H)∣<73∣V(H)∣\sum_{v\in V(H)}\mu(v)=\sum_{v\in V(H)}d_H(v)=2|E(H)|<\frac{7}{3}|V(H)|. We will show that the final charge of each vertex is at least 73\frac{7}{3}, which is a contradiction. The following is the single discharging rule:

(R) Every 3+3^{+}-vertex uu sends charge 16\frac{1}{6} to each nearby 2-vertex vv

(R1) once if vv is on a maximal open thread incident with uu. (R2) twice if vv is on a closed thread incident with uu.

Let uu be a vertex of HH. If dH(u)=2d_H(u)=2, then uu is on a maximal thread TT, so the terminal(s) of TT sends charge a total of 2⋅162\cdot\frac{1}{6} to uu. Thus, μ(u)=2+26=73\mu(u)=2+\frac{2}{6}=\frac{7}{3}.

Suppose dH(u)≥3d_H(u)\ge3, and let uu be responsible for rr nearby 2-vertices. If dH(u)=3d_H(u)=3, then uu is a 3-vertex of G′G'. By Corollary 4.1(ii), uu is not incident with a closed thread. Moreover, by Corollary 4.1(iv), (v), r≤max⁡{2+2+0,2+1+1}=4r\le\max\{2+2+0,2+1+1\}=4, so μ(u)≥3−4⋅16=73\mu(u)\ge3-4\cdot\frac{1}{6}=\frac{7}{3}.

If dH(u)=4d_H(u)=4, then uu is either a 5-vertex of G′G' with a 1-neighbor or a 4-vertex of G′G'. By Corollary 4.1(ii), uu is not incident with a closed thread. Moreover, by Corollary 4.1(v), at most one thread incident with uu is an open 3-thread. Thus r≤3+2+2+2=9r\le3+2+2+2=9, so μ(u)≥4−9⋅16=52>73\mu(u)\ge4-9\cdot\frac{1}{6}=\frac{5}{2}>\frac{7}{3}.

If dH(u)≥5d_H(u)\ge5, then r≤3dH(u)r\le3d_H(u) by Corollary 4.1(iii), so μ(u)=dH(u)−r6≥dH(u)2>73\mu(u)=d_H(u)-\frac{r}{6}\ge\frac{d_H(u)}{2}>\frac{7}{3}.

Hence, every vertex of HH has final charge at least 73\frac{7}{3}.

Four colors for sparse graphs without induced 5-cycles

In this section, we prove Theorem 1.3. We first collect the necessary reducible configurations from § 3.

Corollary 5.1. A strong odd 4-minimal graph with no 5-cycle satisfies the following:

(i) Every vertex has at most one 1-neighbor, and the neighbor of a 1-vertex has even degree at least 4.

(ii) Every closed thread has at most three internal vertices, and its terminal is a 4+^{+}-vertex. Moreover, a 4-vertex with a 1-neighbor is not incident with a closed thread.

(iii) There is no 6+^{+}-thread.

(iv) If uu is a 4-vertex with a 1-neighbor or a 3-vertex, then uu is responsible for at most eight nearby 2-vertices, unless uu is a 3-vertex and the neighbors of uu are on maximal 0-, 4-, 5-threads.

(v) Every 4-vertex is responsible for at most 18 nearby 2-vertices.

(vi) Let vv be the 3+^{+}-neighbor of a 3-vertex uu whose other two neighbors are on maximal 4-, 5-threads. If vv is a 4-vertex with a 1-neighbor or a 3-vertex, then vv is responsible for at most seven nearby 2-vertices.

Proof. (i), (ii), (iii), (v) follow from Lemma 3.1, Lemma 3.2, Lemma 3.4(i), Lemma 3.6, respectively.

(iv): Let uu be a 4-vertex with a 1-neighbor or a 3-vertex. By (ii), uu is not incident with a closed thread. Excluding the possible 1-neighbor of uu, let t1,t2,t3t_1,t_2,t_3 denote the number of 2-vertices on the three maximal threads incident with uu. We may assume t1≤t2≤t3t_1\le t_2\le t_3. By (iii), t3≤5t_3\le5, and by Lemma 3.4(ii), (iii), t2≤4t_2\le4. If t1=0t_1=0, then t1+t2+t3≤0+4+5=9t_1+t_2+t_3\le0+4+5=9, with equality only for (t1,t2,t3)=(0,4,5)(t_1,t_2,t_3)=(0,4,5). If t1≥1t_1\ge1 and t3≤3t_3\le3, then t1≤2t_1\le2 by Lemma 3.5 so t1+t2+t3≤8t_1+t_2+t_3\le8. If t1≥1t_1\ge1 and t3≥4t_3\ge4, then t2≤2t_2\le2 and t1=1t_1=1 by Lemma 3.5, so t1+t2+t3≤8t_1+t_2+t_3\le8. Finally, a 4-vertex with a 1-neighbor is not incident with a 5-thread by Lemma 3.4(iii), so only a 3-vertex can be responsible for nine nearby 2-vertices.

(vi): Suppose that u,vu,v satisfy the hypotheses. By (ii), vv is not incident with a closed thread. Excluding the possible 1-neighbor of vv, let t1,t2,t3t_1,t_2,t_3 denote the number of 2-vertices on the three maximal threads incident with vv. We may assume t1=0t_1=0 and t2≤t3t_2\le t_3. By (iii), t3≤5t_3\le5. By Lemma 3.7, either t2≤2t_2\le2 or t3≤3t_3\le3. Thus t1+t2+t3≤7t_1+t_2+t_3\le7.

Let GG be a graph with mad⁡(G)<115\operatorname{mad}(G)<\frac{11}{5} and no induced 5-cycles. Since a 5-cycle together with a chord has average degree 125>115\frac{12}{5}>\frac{11}{5}, every 5-cycle in GG must be induced, so GG has no 5-cycles. Suppose to the contrary that GG has no strong odd 4-coloring. Choose a strong odd 4-minimal subgraph G′G' of GG. Then G′G' is connected, has no 5-cycles, and mad⁡(G′)<115\operatorname{mad}(G')<\frac{11}{5}. Moreover, G′G' is not a cycle, since every cycle other than a 5-cycle has a strong odd 4-coloring.

Let XX be the set of 1-vertices of G′G', and let H=G′−XH=G'-X. By Corollary 5.1(i), each vertex in XX has a 4+4^+-neighbor, so HH has minimum degree at least 2 and the 2-vertices of HH are exactly the 2-vertices of G′G'. Every 3+3^+-vertex of G′G' remains a 3+3^+-vertex in HH, so the maximal threads containing 2-vertices are unchanged. In particular, every 2-vertex of HH lies on a maximal thread with 3+3^+-terminals in HH. Every 3-vertex of HH is either a 4-vertex of G′G' with a 1-neighbor or a 3-vertex of G′G'. Since the neighbor of a 1-vertex has even degree by Corollary 5.1(i), every 4-vertex of HH is a 4-vertex of G′G'.

Let BB be the set of 3-vertices of HH whose three neighbors are on maximal 0-, 4-, 5-threads. By Corollary 5.1(iv), every vertex of BB is a 3-vertex of G′G'. Each vertex of BB has a unique 3+3^+-neighbor in HH, which is not in BB, by Corollary 5.1(vi).

We obtain our final contradiction via discharging. To each vertex vv of HH, assign an initial charge of dH(v)d_H(v) and let μ(v)\mu(v) denote its final charge after applying the discharging rule. Since the discharging procedure preserves the total charge, we obtain ∑v∈V(H)μ(v)=∑v∈V(H)dH(v)=2∣E(H)∣<115∣V(H)∣\sum_{v\in V(H)}\mu(v)=\sum_{v\in V(H)}d_H(v)=2|E(H)|<\frac{11}{5}|V(H)|. We will show that the final charge of each vertex is at least 115\frac{11}{5}, which is a contradiction. We use the following discharging rules:

(R1) Every 3+3^+-vertex uu sends charge 110\frac{1}{10} to each nearby 2-vertex vv

(R1a) once if vv is on a maximal open thread incident with uu.

(R1b) twice if vv is on a closed thread incident with uu.

(R2) Every 3+3^+-vertex sends charge 110\frac{1}{10} to each neighbor in BB.

Let uu be a vertex of HH. If dH(u)=2d_H(u)=2, then uu is on a maximal thread TT, so the terminal(s) of TT sends charge a total of 2⋅1102\cdot\frac{1}{10} to uu. Thus, μ(u)=2+210=115\mu(u)=2+\frac{2}{10}=\frac{11}{5}. If u∈Bu\in B, then uu sends charge 9⋅1109\cdot\frac{1}{10} by (R1) and receives 110\frac{1}{10} from its unique 3+3^+-neighbor by (R2). Note that uu has no neighbor in BB. Hence μ(u)=3−910+110=115\mu(u)=3-\frac{9}{10}+\frac{1}{10}=\frac{11}{5}.

Suppose that dH(u)≥3d_H(u)\ge3 and u∉Bu\notin B. Let uu be responsible for rr nearby 2-vertices, and let bb be the number of neighbors of uu in BB. Note that uu sends charge (r+b)⋅110(r+b)\cdot\frac{1}{10}. If dH(u)=3d_H(u)=3, then uu is either a 4-vertex with a 1-neighbor in G′G' or a 3-vertex in G′G'. Since u∉Bu\notin B, we know r≤8r\le8 by Corollary 5.1(iv). If b=1b=1, then r≤7r\le7 by Corollary 5.1(vi). If b≥2b\ge2, then since each neighbor in BB is a 3+3^+-vertex, r+b≤5(3−b)+b=15−4b≤7r+b\le5(3-b)+b=15-4b\le7 by Corollary 5.1(iii). Thus, r+b≤8r+b\le8 in every case, so μ(u)≥3−810=115\mu(u)\ge3-\frac{8}{10}=\frac{11}{5}.

If dH(u)=4d_H(u)=4, then r≤18r\le18 by Corollary 5.1(v). If b≥1b\ge1, then r+b≤5(4−b)+b=20−4b≤16r+b\le5(4-b)+b=20-4b\le16 by Corollary 5.1(iii). Thus, r+b≤18r+b\le18 in every case, so μ(u)≥4−1810=115\mu(u)\ge4-\frac{18}{10}=\frac{11}{5}.

If dH(u)≥5d_H(u)\ge5, then Corollary 5.1(iii) gives r+b≤5(dH(u)−b)+b=5dH(u)−4b≤5dH(u)r+b\le5(d_H(u)-b)+b=5d_H(u)-4b\le5d_H(u), so μ(u)≥dH(u)−dH(u)2≥52≥115\mu(u)\ge d_H(u)-\frac{d_H(u)}{2}\ge\frac{5}{2}\ge\frac{11}{5}.

Hence, every vertex of HH has final charge at least 115\frac{11}{5}.

Asymptotically tight bound

In this section, we prove Theorem 1.1. An orientation of a graph gives a direction to each edge. We use a fact attributed to Hakimi [5]. Let Δ+(D)\Delta^{+}(D) denote the maximum outdegree of an orientation DD.

Theorem 6.1 ([5]). Let GG be a graph and let kk be a nonnegative integer. Then GG has an orientation DD with Δ+(D)≤k\Delta^{+}(D) \le k if and only if mad⁡(G)≤2k\operatorname{mad}(G) \le2k.

An edge-coloring of a loopless multigraph is odd if, at each vertex, every color appears 0 or an odd number of times on its incident edges. We use the following theorem of Lužar, Petruševski, and Škrekovski [8].

Theorem 6.2 ([8]). Every loopless multigraph has an odd 6-edge-coloring.

We establish the below statement, from which Theorem 1.1 follows.

Proposition 6.3. For ε∈(0,4)\varepsilon\in(0,4), let r=⌈10−ε+8ε⌉r = \left\lceil10-\varepsilon+\frac{8}{\varepsilon}\right\rceil. If GG is a graph with mad⁡(G)<4−ε\operatorname{mad}(G) < 4-\varepsilon, then χso(G)≤6r\chi_{\mathrm{so}}(G) \le6r.

Proof. Let GG be a graph with mad⁡(G)<4−ε\operatorname{mad}(G) < 4-\varepsilon. Since mad⁡(G)<4\operatorname{mad}(G) < 4, GG has an orientation DD with Δ+(D)≤2\Delta^{+}(D) \le2 by Theorem 6.1. For each vertex yy, let Iy={x∈N(y):x→y is an arc of D}I_y = \{x \in N(y) : x \to y\text{ is an arc of }D\} and Oy={x∈N(y):y→x is an arc of D}O_y = \{x \in N(y) : y \to x\text{ is an arc of }D\}, so IyI_y and OyO_y form a partition of N(y)N(y). Since Δ+(D)≤2\Delta^{+}(D) \le2, we know ∣Oy∣≤2|O_y| \le2 and every vertex of GG belongs to IyI_y for at most two vertices yy.

We define two auxiliary simple graphs H1H_1 and H2H_2 on V(G)V(G). Let uvuv be an edge of H1H_1, if there is a vertex yy, called a 1-witness of uvuv, such that either (u,v)∈Iy×Oy(u,v) \in I_y \times O_y or (u,v)∈Oy×Iy(u,v) \in O_y \times I_y; namely, a path u→y→vu \to y \to v or v→y→uv \to y \to u exists. We claim mad⁡(H1)≤8\operatorname{mad}(H_1) \le8, by showing that H1H_1 has an orientation D1D_1 with Δ+(D1)≤4\Delta^{+}(D_1) \le4 and applying Theorem 6.1. Indeed, for each edge uvuv of H1H_1, choose a 1-witness yy and orient uvuv as follows: u→vu \to v if (u,v)∈Iy×Oy(u,v) \in I_y \times O_y, and v→uv \to u, otherwise. For a vertex uu, d+D1(u)≤∑y:u∈Iy∣Oy∣≤2⋅2=4d^+{_{D_1}}(u) \le\sum_{y:u\in I_y}|O_y| \le2 \cdot2 = 4, so Δ+(D1)≤4\Delta^{+}(D_1) \le4.

Next, let uvuv be an edge of H2H_2 whenever Oy={u,v}O_y = \{u,v\} for some vertex yy, called a 2-witness of uvuv. Since Δ+(D)≤2\Delta^{+}(D) \le2, each vertex of GG determines at most one edge of H2H_2, so distinct edges of H2H_2 have distinct 2-witnesses. Let JJ be a nonempty subgraph of H2H_2 with nn vertices and mm edges, so its average degree is d=2mnd = \frac{2m}{n}. For each edge e=uve=uv of JJ, choose a 2-witness yey_e and let W=V(J)∪{ye:e∈E(J)}W = V(J) \cup\{y_e : e \in E(J)\}. Since the 2-witnesses are distinct, ∣W∣≤n+m|W| \le n+m and ∣E(G[W])∣≥2m|E(G[W])| \ge2m, so

4dd+2=4mn+m≤2∣E(G[W])∣∣W∣≤mad⁡(G)<4−ε.\frac{4d}{d+2} = \frac{4m}{n+m} \le\frac{2|E(G[W])|}{|W|} \le\operatorname{mad}(G) < 4-\varepsilon.

Hence d<8ε−2d < \frac{8}{\varepsilon}-2, and therefore mad⁡(H2)<8ε−2\operatorname{mad}(H_2) < \frac{8}{\varepsilon}-2.

Let H=G∪H1∪H2H = G \cup H_1 \cup H_2. Then

mad⁡(H)≤mad⁡(G)+mad⁡(H1)+mad⁡(H2)<(4−ε)+8+(8ε−2)=10−ε+8ε≤r.\operatorname{mad}(H) \le\operatorname{mad}(G)+\operatorname{mad}(H_1)+\operatorname{mad}(H_2) < (4-\varepsilon)+8+\left(\frac{8}{\varepsilon}-2\right) = 10-\varepsilon+\frac{8}{\varepsilon} \le r.

Thus HH is (r−1)(r-1)-degenerate, so it has a proper rr-coloring ν:V(G)→{1,…,r}\nu:V(G)\to\{1,\ldots,r\}. For each j∈{1,…,r}j \in\{1,\ldots,r\}, let Lj=ν−1(j)L_j=\nu^{-1}(j). Two distinct vertices u,vu,v cannot receive the same color if u,v∈Oyu,v \in O_y since uv∈E(H2)uv \in E(H_2), and if (u,v)∈Iy×Oy(u,v) \in I_y \times O_y since uv∈E(H1)uv \in E(H_1). Therefore, for every vertex yy and j∈{1,…,r}j \in\{1,\ldots,r\}, either Lj∩Oy=∅L_j \cap O_y = \varnothing, or ∣Lj∩Oy∣=1|L_j \cap O_y|=1 and Lj∩Iy=∅L_j \cap I_y=\varnothing. \hfill (∗)(*)

For each j∈{1,…,r}j \in\{1,\ldots,r\}, we construct a loopless multigraph MjM_j, whose edges correspond to the vertices of LjL_j. For every vertex xx, since ∣Ox∣≤2|O_x| \le2, define exe_x as follows:

  • If Ox={y,y′}O_x = \{y,y'\}, then let ex=yy′e_x = yy'.

  • If Ox={y}O_x = \{y\}, then introduce a new vertex zxz_x and let ex=yzxe_x = yz_x.

  • If Ox=∅O_x = \varnothing, then introduce two new vertices zx,zx′z_x,z'_x and let ex=zxzx′e_x = z_xz'_x.

:::♀♀♀♀♀♀ Let MjM_j be the multigraph with vertex set consisting of V(G)V(G) together with all newly introduced vertices, and with edge multiset E(Mj)={ex:x∈Lj}E(M_j)=\{e_x:x\in L_j\}. In particular, x↦exx\mapsto e_x is a bijection between LjL_j and E(Mj)E(M_j). By construction, for every x∈Ljx\in L_j and y∈V(G)y\in V(G), exe_x is incident with yy in MjM_j if and only if x∈Iyx\in I_y. By Theorem 6.2, the multigraph MjM_j has an odd 6-edge-coloring ψj:E(Mj)→{1,…,6}\psi_j:E(M_j)\to\{1,\ldots,6\}.

Finally, we define a 6r6r-coloring φ:V(G)→{1,…,r}×{1,…,6}\varphi:V(G)\to\{1,\ldots,r\}\times\{1,\ldots,6\} of GG where φ(x)=(ν(x),ψν(x)(ex))\varphi(x)=(\nu(x),\psi_{\nu(x)}(e_x)). Since ν\nu is a proper coloring of HH and GG is a subgraph of HH, we know φ\varphi is a proper coloring. We now verify the strong odd condition. Fix v∈V(G)v\in V(G) and consider a color (j,t)(j,t). If Lj∩Ov≠∅L_j\cap O_v\ne\varnothing, then by (∗)(*), Lj∩N(v)L_j\cap N(v) consists of a single vertex, so (j,t)(j,t) appears at most once in N(v)N(v). Otherwise, Lj∩Ov=∅L_j\cap O_v=\varnothing, so Lj∩N(v)=Lj∩IvL_j\cap N(v)=L_j\cap I_v. By the construction of MjM_j, we have

∣{x∈N(v):φ(x)=(j,t)}∣=∣{x∈Lj∩Iv:ψj(ex)=t}∣=∣{e∈E(Mj):v∈e,ψj(e)=t}∣,\left|\{x\in N(v):\varphi(x)=(j,t)\}\right|=\left|\{x\in L_j\cap I_v:\psi_j(e_x)=t\}\right|=\left|\{e\in E(M_j):v\in e,\psi_j(e)=t\}\right|,

which is 00 or odd since ψj\psi_j is an odd edge-coloring. Thus φ\varphi is a strong odd coloring of GG with at most 6r6r colors. □\square

To prove Theorem 1.1, let ε=96c−65+(c−65)2+1152\varepsilon=\frac{96}{c-65+\sqrt{(c-65)^2+1152}}, so ε∈(0,4)\varepsilon\in(0,4) for c≥54c\ge54; equivalently, ε\varepsilon is the positive solution of 10−ε+8ε=c−5610-\varepsilon+\frac{8}{\varepsilon}=\frac{c-5}{6}. Hence, by Proposition 6.3, if mad⁡(G)<4−ε\operatorname{mad}(G)<4-\varepsilon, then χso(G)≤6⌊c−56⌋=6⌊c6⌋≤c\chi_{\mathrm{so}}(G)\le6\left\lfloor\frac{c-5}{6}\right\rfloor=6\left\lfloor\frac{c}{6}\right\rfloor\le c.

Future directions

We conclude with a potential future research direction. For c≥5c\ge5, let mc=inf⁡{mad⁡(G):χso(G)≥c+1}m_c=\inf\{\operatorname{mad}(G):\chi_{\mathrm{so}}(G)\ge c+1\}. In other words, mcm_c is the threshold on the maximum average degree guaranteeing a strong odd cc-coloring. Theorem 1.2 and the construction of Q5Q_5 imply m5=73m_5=\frac{7}{3}. It would be interesting to determine mcm_c for all c≥6c\ge6.

Problem 7.1. Determine mcm_c for all c≥6c\ge6.

In particular, we conjecture m6=187m_6=\frac{18}{7}.

Conjecture 7.2. For a graph GG, if mad⁡(G)<187\operatorname{mad}(G)<\frac{18}{7}, then χso(G)≤6\chi_{\mathrm{so}}(G)\le6.

The bound on the maximum average degree would be best possible. Let Q6Q_6 be the graph obtained from two 4-cycles sharing exactly one vertex and adding an edge between the two vertices farthest away from the shared vertex. Then mad⁡(Q6)=187\operatorname{mad}(Q_6)=\frac{18}{7} and χso(Q6)=7\chi_{\mathrm{so}}(Q_6)=7 as all seven vertices must receive distinct colors in every strong odd coloring of Q6Q_6.

We remark that Conjecture 7.2 holds for every graph GG with Δ(G)≤3\Delta(G)\le3, as Havet [6] proved that G2G^2 is 6-choosable for every graph GG with Δ(G)≤3\Delta(G)\le3 and mad⁡(G)<187\operatorname{mad}(G)<\frac{18}{7}.

Declaration of LLM use.

The authors acknowledge the use of OpenAI’s ChatGPT, which suggested a connection to odd edge-coloring that was helpful in developing the proof of Theorem 1.1 and provided editorial assistance. The authors independently developed and verified all mathematical arguments, revised the exposition, and take full responsibility for the contents of the article.

References

  1. [1]Y. Caro, M. Petruševski, R. Škrekovski, and Z. Tuza, On strong odd colorings of graphs, Discrete Math. 348 (2025), no. 11, 114601.arxiv.org/abs/2410.02336
  2. [2]E.-K. Cho, I. Choi, H. Kwon, and B. Park, Odd coloring of sparse graphs and planar graphs, Discrete Math. 346 (2023), no. 5, 113305.arxiv.org/abs/2202.11267
  3. [3]D. W. Cranston, Odd colorings of sparse graphs, J. Combin. 15 (2024), no. 4, 439–450.arxiv.org/abs/2201.01455
  4. [4]M. Goetze, F. Klute, K. Knauer, I. Parada, J. P. Peña, and T. Ueckerdt, Strong odd coloring in minor-closed classes, 2025, Preprint, arXiv:2505.02736 [math.CO].
  5. [5]S. L. Hakimi, On the degrees of the vertices of a directed graph, J. Frankl. Inst. 279 (1965), no. 4, 290–308.DOI
  6. [6]F. Havet, Choosability of the square of planar subcubic graphs with large girth, Discrete Math. 309 (2009), no. 11, 3553–3563.DOI
  7. [7]H. Kwon and B. Park, Strong odd coloring of sparse graphs, Discrete Math. 349 (2026), no. 11, 115292.arxiv.org/abs/2401.11653
  8. [8]B. Lužar, M. Petruševski, and R. Škrekovski, Odd edge coloring of graphs, Ars Math. Contemp. 9 (2015), no. 2, 267–277.DOI
  9. [9]M. Petruševski and R. Škrekovski, Colorings with neighborhood parity condition, Discrete Appl. Math. 321 (2022), 385–391.arxiv.org/abs/2112.13710
  10. [10]M. Pilipczuk, Strong odd colorings in graph classes of bounded expansion, Electron. J. Combin. 32 (2025), no. 4, P4.14.arxiv.org/abs/2505.15288
  11. [11]K. Santra, An improved upper bound for the strong odd chromatic number of planar graphs, 2026, Preprint, arXiv:2608.03522 [math.CO].arxiv.org/abs/2608.03522

Paper details

vlnc:W_dyu6cnss
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents