Premium
Competition graphs and clique dimensions
Author(s) -
Füredi Zoltán
Publication year - 1990
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240010205
Subject(s) - combinatorics , digraph , mathematics , clique sum , clique , split graph , chordal graph , graph , discrete mathematics , 1 planar graph
Here it is proved that for almost all simple graphs over n vertices one needs Ω( n 4/3 (log n ) −4/3 ) extra vertices to obtain them as a double competition graph of a digraph. on the other hand O ( n 5/3 ) extra vertices are always sufficient. Several problems remain open.