Partitioning perfect graphs into comparability graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915843747610624 |
|---|---|
| author | Gyárfás, András Marits, Márton Tóth, Géza |
| author_facet | Gyárfás, András Marits, Márton Tóth, Géza |
| contents | We study how many comparability subgraphs are needed to partition the edge set of a perfect graph. We show that many classes of perfect graphs can be partitioned into (at most) two comparability subgraphs and this holds for almost all perfect graphs. On the other hand, we prove that for interval graphs an arbitrarily large number of comparability subgraphs might be necessary. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_13523 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Partitioning perfect graphs into comparability graphs Gyárfás, András Marits, Márton Tóth, Géza Combinatorics We study how many comparability subgraphs are needed to partition the edge set of a perfect graph. We show that many classes of perfect graphs can be partitioned into (at most) two comparability subgraphs and this holds for almost all perfect graphs. On the other hand, we prove that for interval graphs an arbitrarily large number of comparability subgraphs might be necessary. |
| title | Partitioning perfect graphs into comparability graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2408.13523 |