The Color Number of Cubic Graphs Having a Spanning Tree with a Bounded Number of Leaves
Analen A. Malnegro, Gina Malacas, Kenta Ozeki · Theory and Applications of Graphs · 2021
The color number c(G) of a cubic graph G is the minimum cardinality of a color class of a proper 4-edge-coloring of G. It is well-known that every cubic graph G satisfies c(G) = 0 if G has a Hamiltonian cycle, and c(G) ≤ 2 if G has a Hamiltonian path. In this paper, we extend these observations by obtaining a bound for the color number of cubic graphs having a spanning tree with a bounded number of leaves.