Přejít k obsahu


On forbidden induced subgraphs for K(1,3)-free perfect graphs

Citace:
BRAUSE, C., HOLUB, P., KABELA, A., RYJÁČEK, Z., SCHIERMEYER, I., VRÁNA, P. On forbidden induced subgraphs for K(1,3)-free perfect graphs. DISCRETE MATHEMATICS, 2019, roč. 342, č. 6, s. 1602-1608. ISSN: 0012-365X
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: On forbidden induced subgraphs for K(1,3)-free perfect graphs
Rok vydání: 2019
Autoři: Christoph Brause , Doc. RNDr. Přemysl Holub Ph.D. , Mgr. Adam Kabela , Prof. RNDr. Zdeněk Ryjáček DrSc. , Ingo Schiermeyer , Mgr. Petr Vrána Ph.D. ,
Abstrakt CZ: V článku studujeme grafy bez {K(1,3),Y}, a ukazujeme, že následující tři tvrzení jsou ekvivalentní: (1) každý souvislý graf bez {K(1,3),Y} s nezávislostí alespoň 3 různý od liché kružnice je perfektní; (2) každý souvislý graf bez {K(1,3),Y} s nezávislostí alespoň 3 různý od liché kružnice omega-obarvitelný; (3) Y je isomorfní s indukovaným podgrafem grafu P(5) nebo Z(2).
Abstrakt EN: We study {K(1,3),Y}-free graphs, and show that the following three statements are equivalent: (1) every connected {K(1,3),Y}-free graph which is distinct from an odd cycle and which has independence number at least 3 is perfect; (2) every connected {K(1,3),Y}-free graph which is distinct from an odd cycle and which has independence number at least 3 is omega-colourable; (3) Y is isomorphic to an induced subgraph of P(5) or Z(2).
Klíčová slova

Zpět

Patička