| Title: | On forbidden induced subgraphs for K(1,3)-free perfect graphs |
| Other Titles: | Zakázané indukované podgrafy pro perfektní grafy bez K(1,3) |
| Authors: | Brause, Christoph Holub, Přemysl Kabela, Adam Ryjáček, Zdeněk Schiermeyer, Ingo Vrána, Petr |
| Citation: | 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. |
| Issue Date: | 2019 |
| Publisher: | Elsevier |
| Document type: | článek article |
| URI: | 2-s2.0-85062663356 http://hdl.handle.net/11025/34732 |
| ISSN: | 0012-365X |
| Keywords: | Perfektní graf;vrcholové obarvení;zakázaný idukovaný podgraf |
| Keywords in different language: | Perfect graph;vertex colouring;forbidden induced subgraph |
| Abstract: | 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). |
| Abstract in different language: | 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). |
| Rights: | Plný text není přístupný. © Elsevier |
| Appears in Collections: | Články / Articles (KMA) OBD |
Files in This Item:
| File | Size | Format | |
|---|---|---|---|
| 1-s2.0-S0012365X19300470-main.pdf | 545,5 kB | Adobe PDF | View/Open Request a copy |
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11025/34732Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.