AN EXACT BOUND ON THE NUMBER OF PROPER 3-EDGE-COLORINGS OF A CONNECTED CUBIC GRAPH

The paper examines the question of an upper bound on the number of proper edge 3-colorings of a connected cubic graph with 2n vertices. For this purpose, the Karpov method is developed with the help of which a weaker version of the bound was previously obtained. Then the bound [2.sup.n] + 8 for even n and [2.sup.n] + 4 for odd n is proved. Moreover, a unique example is found, for which the upper bound is exact. Bibliography: 2 titles.
1. INTRODUCTION In paper [1], Karpov studies proper 3-edge-colorings of a connected cubic graph (in such a coloring each edge is colored in one of three fixed colors so that [...]