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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom