Cambiar a contenido. | Saltar a navegación

Herramientas Personales
Entrar

Navegación

Usted está aquí: Inicio / Actividades / Seminarios / 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
Ponente:
Cuándo 06/06/2012
de 18:00 a 19:00
Dónde Sala de café, Instituto de Matemáticas
Nombre
Agregar evento al calendario 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.

archivado en: