| Název: | On forbidden induced subgraphs for K(1,3)-free perfect graphs |
| Další názvy: | Zakázané indukované podgrafy pro perfektní grafy bez K(1,3) |
| Autoři: | Brause, Christoph Holub, Přemysl Kabela, Adam Ryjáček, Zdeněk Schiermeyer, Ingo Vrána, Petr |
| Citace zdrojového dokumentu: | 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. |
| Datum vydání: | 2019 |
| Nakladatel: | Elsevier |
| Typ dokumentu: | článek article |
| URI: | 2-s2.0-85062663356 http://hdl.handle.net/11025/34732 |
| ISSN: | 0012-365X |
| Klíčová slova: | Perfektní graf;vrcholové obarvení;zakázaný idukovaný podgraf |
| Klíčová slova v dalším jazyce: | Perfect graph;vertex colouring;forbidden induced subgraph |
| Abstrakt: | 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 v dalším jazyce: | 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). |
| Práva: | Plný text není přístupný. © Elsevier |
| Vyskytuje se v kolekcích: | Články / Articles (KMA) OBD |
Soubory připojené k záznamu:
| Soubor | Velikost | Formát | |
|---|---|---|---|
| 1-s2.0-S0012365X19300470-main.pdf | 545,5 kB | Adobe PDF | Zobrazit/otevřít Vyžádat kopii |
Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam:
http://hdl.handle.net/11025/34732Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.