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.
No takes yet. Share an insight, caveat, or question.
Gyárfás et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: