Cuando las etiquetas de las aristas pertenecen a un conjunto ordenado (es decir, los números reales), ésta puede ser llamada como grafo ponderado.[2] Para muchas aplicaciones, a las aristas y los vértices le corresponde etiquetas que tienen un significado en el dominio asociado.Por ejemplo, las aristas pueden ser asignadas mediante pesos que representan el «coste» de atravesar entre los vértices implicados.[5] Rosa identificó tres tipos de etiquetado, a los cuales llamó α-, β-, y ρ-etiquetado.[6] Los β-etiquetados fueron más tarde renombrados como elegantes por S. W. Golomb y el nombre se ha hecho popular desde entonces.es elegante si y sólo si existe una inyección que induce una biyección de E a los enteros positivos hastaEn su trabajo original, Rosa demostró que todos los grafos eulerianos con orden equivalente a 1 o 2 (mod 4) no son elegantes.Esto ha sido demostrado para todos los caminos, orugas, y muchas otras familias infinitas de los árboles.El mismo Kotzig ha llamado al esfuerzo de demostrar la conjetura una «enfermedad».La coloración de grafos es un caso especial de grafos etiquetados, tales que los vértices adyacentes y las aristas coincidentes deben tener diferentes etiquetas.
Un etiquetado elegante. Las etiquetas de los vértices están en negro, las etiquetas de las aristas en rojo.
Una coloración por vértices para un
grafo de Petersen
, donde cada color representa una etiqueta.
