Leírás
Pach and Törőcsik proved in 1993 that any set of $n$ convex sets in the plane contains $n^{1/5}$ pairwise disjoint or pairwise crossing. The main idea was that they decomposed the disjointness graph of the sets into $4$ comparability graphs.
This idea and result had many applications and generalizations and motivates the following general problem: how many comparability graphs are needed to cover (or partition) the edge set of a graph. The most interesting case is the class of perfect graphs. We show that for almost all perfect graphs, two comparability graphs are enough. However, there are some perfect graphs (interval graphs) where arbitrarily many comparability graphs are needed.
We do not know any perfect graph where the partition and the covering numbers are different. For not necessarily perfect graphs these parameters can be different: we show an example where the covering number is $2$ and the partition number is $3$. This is a very weak result, a lot of questions are still open.
Joint work with Márton Marits and András Gyárfás.
The talk will also be broadcast on Zoom.