Sobre coloraciones completas y gráficas perfectas

Sea G una gráfica simple. Una coloración en sus vértices es llamada completa si cada pareja de colores están en una arista. El número pseudoacromático ψ(G) es el máximo k para el cual existe una coloración completa de G. Si la coloración es propia (es decir, cada clase cromática es independiente) entonces tal máximo se conoce como el número acromático α(G). Una coloración Grundy de una gráfica G es una coloración propia de vértices de G (cuyos colores son enteros positivos) de tal forma que para cada dos colores i y j (tal que i<j) cada vértice coloreado con el color j tiene un vecino con el color i. Consecuentemente, cada coloración Grundy es una coloración completa. El número Grundy Γ(G) es el máximo entero positivo k para el cual una gráfica G tiene una coloración Grundy con k colores. Claramente,

ω(G)≤χ(G)≤Γ(G)≤α(G)≤ψ(G),

donde ω(G) denota el número de clan y χ(G) denota el número cromático. Para a y b distintos miembros de {ω,χ,Γ,α,ψ}, una gráfica es llamada ab-perfecta si para cada subgráfica inducida H de G, a(H)=b(H). Una gráfica χω-perfecta es usualmente llamada gráfica perfecta. En esta dirección, damos caracterizaciones de las gráficas ψω-perfectas.