En teoría de grafos , la coloración de gráficos orientada es un tipo especial de coloración de gráficos . Es decir, es una asignación de colores a los vértices de un gráfico orientado que
De manera equivalente, una coloración de gráfico orientado de un gráfico G es un gráfico orientado H (cuyos vértices representan colores y cuyos arcos representan orientaciones válidas entre colores) de modo que existe un homomorfismo de G a H.
Un número cromático orientado de un gráfico G es la menor cantidad de colores necesarios en una coloración orientada; normalmente se denota por . La misma definición también se puede extender a gráficos no dirigidos, definiendo el número cromático orientado de un gráfico no dirigido como el número cromático orientado más grande de cualquiera de sus orientaciones . [1]
El número cromático orientado de un ciclo 5 dirigido es cinco. Si el ciclo está coloreado con cuatro o menos colores, entonces dos vértices adyacentes tienen el mismo color o dos vértices separados por dos pasos tienen el mismo color. En el último caso, los bordes que conectan estos dos vértices con el vértice entre ellos están orientados de manera inconsistente: ambos tienen el mismo par de colores pero con orientaciones opuestas. Por tanto, no es posible colorear con cuatro o menos colores. Sin embargo, darle a cada vértice su propio color único conduce a una coloración orientada válida.
Una coloración orientada sólo puede existir para un gráfico dirigido sin bucles o 2 ciclos dirigidos. Porque, un bucle no puede tener diferentes colores en sus puntos finales, y un ciclo de 2 no puede tener ambos bordes orientados consistentemente entre los mismos dos colores. Si se cumplen estas condiciones, entonces siempre existe una coloración orientada, por ejemplo la coloración que asigna un color diferente a cada vértice.
Si una coloración orientada es completa , en el sentido de que no se pueden fusionar dos colores para producir una coloración con menos colores, entonces corresponde únicamente a un homomorfismo de grafo en un torneo . El torneo tiene un vértice para cada color del colorante. Para cada par de colores, hay una arista en el gráfico coloreado con esos dos colores en sus puntos finales, lo que le da orientación a la arista en el torneo entre los vértices correspondientes a los dos colores. Las coloraciones incompletas también pueden representarse mediante homomorfismos en torneos, pero en este caso la correspondencia entre coloraciones y homomorfismos no es uno a uno.
Los gráficos no dirigidos de género acotado , grado acotado o número cromático acíclico acotado también tienen número cromático orientado acotado. [1]
