A Linear Heterochromatic Number of Graphs
Por:
Montellano-Ballesteros J.J., Neumann-Lara V.
Publicada:
1 ene 2003
Resumen:
Let G = (V(G),E(G)) be a multigraph with multiple loops allowed, and V 0 ? V(G). We define h(G, V0) 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 V0 receive different colours. In this paper we prove that if each x ? V0 is incident to at least two edges of G, then h(G, V0) = ?(G[V0]) + |E(G)| - |V0| + 1 where ?(G[V0]) is the maximum cardinality of a set of mutually disjoint cycles (of length at least two) in the subgraph induced by V0.
Filiaciones:
Montellano-Ballesteros J.J.:
Instituto de Matemáticas, UNAM, Cd. Universitaria, Circuito Exterior, México 04510, DF, Mexico
Neumann-Lara V.:
Instituto de Matemáticas, UNAM, Cd. Universitaria, Circuito Exterior, México 04510, DF, Mexico
|