Can I read Odd Edge-colorings of Subdivisions of Odd Graphs on EtoBox?

Odd Edge-colorings of Subdivisions of Odd Graphs by Petruševski, Mirko; Škrekovski, Riste is a scholarly article available to read on EtoBox.

What is Odd Edge-colorings of Subdivisions of Odd Graphs about?

An odd graph is a finite graph all of whose vertices have odd degrees. Given graph $G$ is decomposable into $k$ odd subgraphs if its edge set can be partitioned into $k$ subsets each of which induces an odd subgraph of $G$. The minimum value of $k$ for which such a decomposition of $G$ exists is the odd chromatic index, $\chi_{o}'(G)$, introduced by Pyber (1991). For every $k\geq\chi_{o}'(G)$, the graph $G$ is said to be odd $k$-edge-colorable. Apart from two particular exceptions, which are respectively odd $5$- and odd $6$-edge-colorable, the rest of connected loopless graphs are odd $4$-edge-colorable, and moreover one of the color classes can be reduced to size $\leq2$. In addition, it has been conjectured that an odd $4$-edge-coloring with a color class of size at most $1$ is always achievable. Atanasov et al. (2016) characterized the class of subcubic graphs in terms of the value $\chi_{o}'(G)\leq4$. In this paper, we extend their result to a characterization of all subdivisions of odd graphs in terms of the value of the odd chromatic index. This larger class $\mathcal{S}$ is of a particular interest as it collects all `least instances' of non-odd graphs. As a prelude to our

Author

Petruševski, Mirko; Škrekovski, Riste

Published

2021

Language

EN