Competition graphs and clique dimensions |
| |
Authors: | Zolt n Fü redi |
| |
Affiliation: | Zoltán Füredi |
| |
Abstract: | Here it is proved that for almost all simple graphs over n vertices one needs Ω(n4/3(log n)?4/3) extra vertices to obtain them as a double competition graph of a digraph. on the other hand O(n5/3) extra vertices are always sufficient. Several problems remain open. |
| |
Keywords: | |
|
|