UNAM
You are here: Home / Actividades académicas / Seminarios en C.U. / Seminario de Becarios / Actividades del Seminario de Becarios / Sobre coloraciones completas y gráficas perfectas

Sobre coloraciones completas y gráficas perfectas

Christian Rubio (IMUNAM-CU) - miércoles 6 de junio de 2012, 18hrs

When Jun 06, 2012
from 06:00 PM to 07:00 PM
Where Sala de café, Instituto de Matemáticas
Contact Name
Add event to calendar vCal
iCal

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.

Filed under: