A Linear Heterochromatic Number of Graphs

Let G=(V(G),E(G)) be a multigraph with multiple loops allowed, and V ₀V(G). We define h(G,V ₀) to be the minimum integer k such that for every edge-colouring of G using exactly k colours, all the edges incident with some vertex in V ₀ receive different colours. In this paper we prove that if each xV ₀ is incident to at least two edges of G, then h(G,V ₀)=(G[V ₀])+|E(G)|–|V ₀|+1 where (G[V ₀]) is the maximum cardinality of a set of mutually disjoint cycles (of length at least two) in the subgraph induced by V ₀. Acknowledgments.We thank the referee for suggesting us a short alternative proof of our main theorem.