Partitioning perfect graphs into comparability graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |