Odd edge‐colorings of subdivisions of odd graphs

Petrushevski, Mirko; Škrekovski, Riste

doi:10.1002/jgt.22991

Odd edge‐colorings of subdivisions of odd graphs

Journal

Journal of Graph Theory

Date Issued

2023-05-29

Author(s)

Škrekovski, Riste

DOI

10.1002/jgt.22991

Abstract

AbstractAn odd graph is a finite graph all of whose vertices have odd degrees. A graph is decomposable into odd subgraphs if its edge set can be partitioned into subsets each of which induces an odd subgraph of . The minimum value of for which such a decomposition of exists is the odd chromatic index, , introduced by Pyber. For every , the graph is said to be odd ‐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 . 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. characterized the class of loopless subcubic graphs in terms of the value . In this paper, we extend their result to a characterization of all loopless subdivisions of odd graphs in terms of the value of the odd chromatic index. This larger class is of a particular interest as it collects all “least instances” of nonodd graphs. As a prelude to our main result, we show that every connected graph requiring the maximum number of four colors, becomes odd 3‐edge‐colorable after removing a certain edge. Thus, we provide support for the mentioned conjecture by proving it for all subdivisions of odd graphs. The paper concludes with few problems for possible further work.