Seminár z teórie grafov - Christian Rubio-Montiel (10.3.2016)

vo štvrtok 10.3.2016 o 9:50 hod. v miestnosti M/213

08. 03. 2016 10.54 hod.
Od: Martin Škoviera

Prednášajúci: Christian Rubio-Montiel (Instituto de Matematicas, UNAM, Mexico a UK, Bratislava)

Názov: ab-Perfect graphs

Termín: 10.3.2016, 9:50 hod., M/213

Abstrakt:
A graph G is called ab-perfect if a(H) equals b(H) for any induced subgraph H of G and any two different parameters "a" and "b" of G. With this definition, perfect graphs are the wX-perfect graphs where "w" is the clique number and "X" is the chromatic number. In this presentation, we give forbidden graphs characterizations for several classes of ab-perfect graphs when "a" and "b" are parameters related to the clique number, complete colorings -- any two colors have an edge in common-- and the Hadwiger number -- the order of the largest complete minor of a graph. We also show that some classes of graphs such as chordal graphs, cographs and trivially perfect graphs are a type of ab-perfect graphs.