Strong odd coloring of sparse graphs

It is enough to assume that $|A_{i}|=2$ for each $i\in\{1,\ldots,d-1\}$. Fix $\alpha\in A_{d}$. Then we define a loopless multigraph $G$ with $V(G)=\cup_{i=1}^{d}A_{i}$ and $E(G)=\{A_{1},\ldots,A_{d-1}\}$. Note that it is sufficient to find an orientation $D$ of $G$ such that $\deg_{D}^{-}(\alpha)$ is even and $\deg_{D}^{-}(x)$ is either odd or $0$ for every $x\in V(G)\setminus\{\alpha\}$, by taking the head of the arc $\overrightarrow{A_{i}}$ of $D$ as a representative of $A_{i}$ for each $i\in\{1,\ldots,d-1\}$.

To find such orientation $D$ of $G$, we will find an ordering $v_{1},\ldots,v_{|V(G)|}$ of the vertices of $G$ as follows. Let $v_{1}=\alpha$. If $N_{G}(v_{i})-\{v_{1},\ldots,v_{i}\}=\emptyset$, then take any vertex in $V(G)-\{v_{1},\ldots,v_{i}\}$ as $v_{i+1}$. If $N_{G}(v_{i})-\{v_{1},\ldots,v_{i}\}\neq\emptyset$, then we take $v_{i+1}\in N_{G}(v_{i})-\{v_{1},\ldots,v_{i}\}$ and then choose an edge $e_{i}$ joining $v_{i}$ and $v_{i+1}$. Let $L$ be the set of such chosen edges $e_{i}$, and note that $L$ induces a linear forest of $G$.

For simplicity, let $G_{i}$ be the spanning subgraph of $G$ induced by $E(G)\setminus\{e_{j}\in L\mid j>i\}$ for each $i\geq 0$. We will define an orientation $D_{i}$ of $G_{i}$ for each $i$, as follows. First, we define an orientation $D_{0}$ of $G_{0}$ by $A(D_{0})=\{(v_{i},v_{j})\mid i>j,v_{i}v_{j}\in E(G_{0})\}$. Suppose that $D_{i-1}$ is defined. If $G_{i}=G_{i-1}$, then we define $D_{i}=D_{i-1}$. If $G_{i}\neq G_{i-1}$, then $E(G_{i})=E(G_{i-1})\cup\{e_{i}\}$, and so we define $D_{i}$ so that $A(D_{i})=A(D_{i-1})\cup\{\overrightarrow{e_{i}}\}$, where

It remains to show $D:=D_{|V(G)|-1}$ is a desired orientation, that is, satisfying the condition that $\deg_{D}^{-}(v_{1})$ is even and $\deg_{D}^{-}(v_{i})$ is either odd or $0$ for every $i\geq 2$. Take a vertex $v_{i}$. Suppose that the edge $e_{i}$ exists. By the definition of $D_{i}$,

Hence it satisfies the condition. Suppose that the edge $e_{i}$ does not exist. If $i=1$, then $\deg_{G}(v_{1})=0$ and so $\deg_{D}^{-}(v_{1})=0$. If $i>1$, then $N_{G}(v_{i})-\{v_{1},\ldots,v_{i}\}=\emptyset$, and so it always holds that $\deg_{D}^{-}(v_{i})\in\{0,1\}$. Hence, it completes the proof. ∎

Suppose that such coloring $\varphi$ exists. Then by coloring $x$ with a color in $A_{\varphi}(x)$, we obtain an SO $(\Delta+c)$-coloring of G. It is a contradiction to the fact that $G$ has no SO $(\Delta+c)$-coloring. ∎

In each proof, we consider an SO $(\Delta+c)$-coloring $\varphi$ of $G^{\prime}=G-S$ for some $\emptyset\neq S\subset V(G)$, and then we finish the proof by coming up with an SO $(\Delta+c)$-coloring of $G$, which is a contradiction. See Figure 3.

(i) It is clear that $G$ has no isolated vertex. Suppose to the contrary that $G$ has a $1$-vertex $u$ with neighbor $v$. Let $S=\{u\}$. Since $|A_{\varphi}(v)|\geq c$ by (2.1), we color $u$ with a color in $A_{\varphi}(v)$, which gives an SO $(\Delta+c)$-coloring of $G$.

(ii) Suppose to the contrary that $G$ has a triangle $v_{1}v_{2}v_{3}v_{1}$ such that $v_{2}$ is a $(c+1)^{-}$-vertex and $v_{3}$ is a $2$-vertex. For an SO $(\Delta+c)$-coloring $\varphi$ of $G-v_{3}$, $|A_{\varphi}(v_{3})|\geq\Delta+c-(\Delta+c-1)\geq 1$ by (2.1). Since $v_{1}v_{2}\in E(G^{\prime})$, $\varphi(v_{1})\neq\varphi(v_{2})$. It is a contradiction by Lemma 2.2.

(iii) Suppose to the contrary that $G$ has two vertices $x$ and $y$ with three common $2$-neighbors $v_{1}$, $v_{2}$, and $v_{3}$. Let $S=\{v_{2},v_{3}\}$. Then color $v_{2}$ and $v_{3}$ with the same color of $v_{1}$ to obtain an SO $(\Delta+c)$-coloring of $G$.

(iv) Suppose to the contrary that $G$ has a $d_{d-1}$-vertex $u$ with only $(\Delta+c-d)^{-}$-neighbors for some $2\leq d\leq\Delta$. Let $v_{1},\ldots,v_{d-1}$ be $2$-neighbors of $u$ and $v^{\prime}$ be the other neighbor of $u$. For each $i\in\{1,\ldots,d-1\}$, let $w_{i}$ be the neighbor of $v_{i}$ other than $u$. Note that $v_{i}\neq w_{j}$ for each $i,j\in\{1,\ldots,d-1\}$ by (ii). Let $S=\{u,v_{1},\ldots,v_{d-1}\}$. Note that $|A_{\varphi}(u)|\geq\Delta+c-(\Delta+d-1)\geq 1$, and $A_{\varphi}(v_{i})\geq\Delta+c-(\Delta+1)=c-1\geq 2$ for each $i\in\{1,\ldots,d-1\}$ by (2.1). We color $u$ with a color $\gamma$ in $A_{\varphi}(u)$. Let $X$ be the set of all pairs $(i,j)$ such that $w_{i}=w_{j}$ and $i<j$. Note that by (iii), each $i\in\{1,\ldots,d-1\}$ appears at most once as an entry of an element of $X$. Moreover, when $(i,j)\in X$, it holds that $A_{\varphi}(v_{i})=A_{\varphi}(v_{j})$ and $|A_{\varphi}(v_{i})|=|A_{\varphi}(v_{j})|\geq c$ by (2.1).

If $c=3$ and $X\neq\emptyset$, then $X=\{(1,2)\}$, $d=3$, and so we can color $v_{1}$, $v_{2}$ with distinct colors in $A_{\varphi}(v_{1})\setminus\{\gamma\}$ to obtain an SO $(\Delta+c)$-coloring of $G$. Suppose that $c\geq 4$ or $X=\emptyset$. Let $A_{i}:=(A_{\varphi}(v_{i})\cup\{\varphi(v^{\prime})\})\setminus\{\gamma\}$ for each $i\in\{1,\ldots,d-1\}$, and $A_{d}:=\{\varphi(v^{\prime})\}$. Since $v^{\prime}$ is a neighbor of $v_{i}$ in $G^{2}$, $\varphi(v^{\prime})\not\in A_{\varphi}(v_{i})$. It follows that $|A_{i}|=|A_{\varphi}(v_{i})|\geq 2$ for each $i\in\{1,\ldots,d-1\}$. If $(i,j)\in X$, then $X\neq\emptyset$ and so $|A_{i}|=|A_{\varphi}(v_{i})|\geq c\geq 4$, and then we redefine $A_{i}:=A^{\prime}_{i}$ and $A_{j}:=A^{\prime}_{j}$ for some disjoint subsets $A^{\prime}_{i},A^{\prime}_{j}$ of $A_{i}$ of size two. By applying Lemma 2.1, there is a system of odd representative $(\beta_{1},\ldots,\beta_{d-1},\alpha)$ for $(A_{1},\ldots,A_{d-1},A_{d})$, where $\alpha=\varphi(v^{\prime})$. Then, coloring $v_{i}$ with $\beta_{i}$ results in an SO $(\Delta+c)$-coloring of $G$. ∎

Suppose to the contrary that $G$ has adjacent two $3_{1}$-vertices $u_{1}$ and $u_{2}$. For each $i\in\{1,2\}$, let $v_{i}$ be the $2$-neighbor of $u_{i}$, $u^{\prime}_{i}$ be the neighbor of $u_{i}$ other than $v_{i}$ and $u_{3-i}$, and $w_{i}$ be the neighbor of $v_{i}$ other than $u_{i}$. See Figure 4. Note that $v_{1}\neq v_{2}$ by Lemma 2.3 (ii). Thus $u_{1}$, $u_{2}$, $v_{1}$, and $v_{2}$ are distinct, and we let $S=\{u_{1},u_{2},v_{1},v_{2}\}$. In addition, $w_{i}\neq u_{3-i}$ (equivalently, $u^{\prime}_{3-i}\neq v_{i}$) and $w_{i}\neq v_{3-i}$ for each $i\in\{1,2\}$ by [C2]. Thus $S\cap\{u^{\prime}_{1},u^{\prime}_{2},w_{1},w_{2}\}=\emptyset$.

Note that $|A_{\varphi}(u_{i})|\geq 2$ and $|A_{\varphi}(v_{i})|\geq 3$ for each $i\in\{1,2\}$ by (2.1). We color $u_{1}$, $u_{2}$, $v_{1}$ with a color in $A_{\varphi}(u_{1})$, $A_{\varphi}(u_{2})$, $A_{\varphi}(v_{1})$, respectively, so that colors of $u_{1}$, $u_{2}$, $v_{1}$ are distinct. Then the resulting coloring is an SO $(\Delta+4)$-coloring of $G-v_{2}$, which contradicts to Lemma 2.2. ∎

Suppose to the contrary that $G$ has a path path $v_{1}v_{2}v_{3}v_{4}$ such that $v_{1}$ is a $2$-vertex and $v_{i}$ is a $3$-vertex for each $i\in\{2,3,4\}$, where $v_{4}$ is a common neighbor of $v_{3}$ and either $v_{1}$ or $v_{2}$. Other neighbors of $v_{i}$’s are labeled as Figure 5. Let $S=\{v_{1},v_{2},v_{3},v_{4}\}$. By Lemma 2.3 (ii), $S\cap\{w,w_{3},w_{4}\}=\emptyset$. Note that $|A_{\varphi}(v_{1})|\geq 4$, $|A_{\varphi}(v_{2})|\geq 3$, $|A_{\varphi}(v_{3})|\geq 2$, and $|A_{\varphi}(v_{4})|\geq 3$ by (2.1). Then it is possible to color $v_{i}$ with a color in $A_{\varphi}(v_{i})$ for each $i\in\{1,2,3,4\}$ so that the colors of $v_{i}$’s are distinct. It results in an SO $(\Delta+4)$-coloring of $G$. ∎

Suppose to the contrary that $G$ has a $3$-vertex $u$ with two $3_{1}$-neighbors $v_{1}$ and $v_{2}$. We follow the labeling of the vertices as Figure 6. Let $S=\{u,v_{1},v_{2},v^{\prime}_{1},v^{\prime}_{2}\}$. By Lemma 3.2, $v^{\prime}_{1}\neq v^{\prime}_{2}$, and so $S$ has five distinct vertices. Note that for each $i\in\{1,2\}$, $v_{i}\notin\{w_{3-i},x_{3-i}\}$ by Lemma 3.2. Also, $u\neq w_{i}$, $v^{\prime}_{i}\neq v$ by Lemma 2.3 (ii), and $v^{\prime}_{i}\notin\{w_{3-i},x_{3-i}\}$ by Lemma 2.3 (iv). Thus $S\cap\{w_{1},w_{2},x_{1},x_{2},v\}=\emptyset$. Note that $|A_{\varphi}(u)|\geq 2$, $|A_{\varphi}(v_{i})|\geq 2$, and $|A_{\varphi}(v^{\prime}_{i})|\geq 3$ for each $i\in\{1,2\}$ by (2.1).

First, we color $u$ with a color $\gamma$ in $A_{\varphi}(u)$. For simplicity, let $A_{i}=A_{\varphi}(v_{i})\cup\{\varphi(v)\}\setminus\{\gamma\}$ for each $i\in\{1,2\}$. Since $\varphi(v)\notin A_{\varphi}(v_{i})$, $|A_{i}|\geq 2$ for each $i\in\{1,2\}$. Let $A_{3}=\{\varphi(v)\}$. If $x_{1}\neq x_{2}$, then we apply Lemma 2.1 to obtain a system of odd representative $(\beta_{1},\beta_{2},\alpha)$ for $(A_{1},A_{2},A_{3})$, where $\alpha=\varphi(v)$. If $x_{1}=x_{2}$, then $|A_{\varphi}(v_{i})|\geq 3$ for each $i\in\{1,2\}$ by (2.1), and so we choose $\beta_{i}$ in $A_{\varphi}(v_{i})\setminus\{\gamma\}$ for each $i\in\{1,2\}$ so that $\beta_{1}\neq\beta_{2}$. Then we color $v_{i}$ with $\beta_{i}$ in $A_{i}$ for each $i\in\{1,2\}$. We denote this coloring of $G-\{v^{\prime}_{1},v^{\prime}_{2}\}$ by $\varphi$ again. Then $|A_{\varphi}(v^{\prime}_{i})|\geq 1$ for each $i\in\{1,2\}$ by (2.1) and so we color $v^{\prime}_{1}$ with a color in $A_{\varphi}(v^{\prime}_{1})$. Then the resulting coloring is an SO $(\Delta+4)$-coloring of $G-v^{\prime}_{2}$, which contradicts to Lemma 2.2. ∎

Suppose to the contrary that $G$ has a $4$-vertex $u$ with two $2$-neighbors $v_{1}$, $v_{2}$ and one $3_{1}$-neighbor $v_{3}$. We follow the labeling of the vertices as Figure 7. Let $S=\{u,v_{1},v_{2},v_{3},x\}$. Note that $x\neq v_{i}$ for each $i\in\{1,2\}$ by Lemma 2.3 (ii), and so $S$ has five distinct vertices. For each $i\in\{1,2\}$, note that $u\neq y$ and $v_{3}\neq w_{i}$ by Lemma 2.3 (ii). Also, $v_{i}\notin\{w_{3},w_{3-i},y\}$, $x\notin\{w_{1},w_{2},v\}$ by Lemma 2.3 (iv). Thus $S\cap\{w_{1},w_{2},w_{3},y,v\}=\emptyset$. Note that $|A_{\varphi}(u)|\geq 1$, $|A_{\varphi}(v_{i})|\geq 3$ for each $i\in\{1,2\}$, $|A_{\varphi}(v_{3})|\geq 2$, and $|A_{\varphi}(x)|\geq 3$ by (2.1).

First, we color $u$ with a color $\gamma$ from $A_{\varphi}(u)$. For simplicity, let $A_{i}=A_{\varphi}(v_{i})\cup\{\varphi(v)\}\setminus\{\gamma\}$ for each $i\in\{1,2,3\}$. Since $\varphi(v)\notin A_{\varphi}(v_{i})$ for each $i\in\{1,2,3\}$, $|A_{i}|\geq 3$ for each $i\in\{1,2\}$ and $|A_{3}|\geq 2$. Let $A_{4}=\{\varphi(v)\}$. We color $v_{1},v_{2},v_{3}$ as follows.

If $w_{1}=w_{2}=w_{3}$, then $A_{1}=A_{2}$ and $A_{3}\subset A_{1}$, and so we color $v_{i}$’s with a same color $\beta\in A_{3}\setminus\{\varphi(v)\}$. Suppose that it is not the case of $w_{1}=w_{2}=w_{3}$. Without loss of generality, let $w_{2}\neq w_{3}$. We take subsets $A^{\prime}_{2}$ and $A^{\prime}_{3}$ of $A_{2}$ and $A_{3}$, respectively, of size exactly two. If $w_{1}=w_{j}$ for some $j\in\{2,3\}$, then $|A_{1}|\geq 4$ and so we take a subset $A^{\prime}_{1}$ of $A_{1}\setminus A^{\prime}_{j}$ of size two. If $w_{1}\neq w_{j}$ for each $j\in\{2,3\}$, then let $A^{\prime}_{1}=A_{1}$. Now, we apply Lemma 2.1 to obtain a system of odd representative $(\beta_{1},\beta_{2},\beta_{3},\varphi(v))$ for $(A^{\prime}_{1},A^{\prime}_{2},A^{\prime}_{3},A_{4})$. We color $v_{i}$ with $\beta_{i}$ for each $i\in\{1,2,3\}$. Then the resulting coloring is an SO $(\Delta+4)$-coloring of $G-x$, which is a contradiction to Lemma 2.2. ∎