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.
No takes yet. Share an insight, caveat, or question.
Malnegro et al. (2021) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: