Odd Edge Colorings of Graphs with Odd Order
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918452233502720 |
|---|---|
| author | Kano, Mikio Maezawa, Shun-ichi Ozeki, Kenta |
| author_facet | Kano, Mikio Maezawa, Shun-ichi Ozeki, Kenta |
| contents | An {\em odd subgraph} of a graph is a subgraph in which every vertex has odd degree. A graph $G$ is said to be {\em odd $k$-edge-colorable} if there exists an edge-coloring $E(G) \rightarrow \{1,2, \ldots, k\}$ such that each non-empty color class induces an odd subgraph of $G$. The {\em odd chromatic index} of $G$, denoted by $χ'_o(G)$, is the minimum $k$ for which $G$ is odd $k$-edge-colorable. In this paper, we prove that every $4$-connected simple graph of odd order is odd 3-edge-colorable, and show that the $4$-connectedness assumption is necessary. We also prove that for a connected Eulerian graph $G$ of odd order, there exists an edge $e$ such that $G-e$ is odd $2$-edge-colorable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_15824 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Odd Edge Colorings of Graphs with Odd Order Kano, Mikio Maezawa, Shun-ichi Ozeki, Kenta Combinatorics An {\em odd subgraph} of a graph is a subgraph in which every vertex has odd degree. A graph $G$ is said to be {\em odd $k$-edge-colorable} if there exists an edge-coloring $E(G) \rightarrow \{1,2, \ldots, k\}$ such that each non-empty color class induces an odd subgraph of $G$. The {\em odd chromatic index} of $G$, denoted by $χ'_o(G)$, is the minimum $k$ for which $G$ is odd $k$-edge-colorable. In this paper, we prove that every $4$-connected simple graph of odd order is odd 3-edge-colorable, and show that the $4$-connectedness assumption is necessary. We also prove that for a connected Eulerian graph $G$ of odd order, there exists an edge $e$ such that $G-e$ is odd $2$-edge-colorable. |
| title | Odd Edge Colorings of Graphs with Odd Order |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2604.15824 |