Partitioning perfect graphs into comparability graphs

2024/08/24 by Gyárfás, András, Marits, Márton, Tóth, Géza
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2408.13523

Abstract

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.

Related

• Characterization of Split Comparability Graphs
• Perfect matching cuts partitioning a graph into complementary subgraphs
• Comparability and Cocomparability Bigraphs
• The Satisfactory Partition Problem
• Comparability digraphs: An analogue of comparability graphs