Premium
Graphs with Few 3‐Cliques and 3‐Anticliques are 3‐Universal
Author(s) -
Linial Nati,
Morgenstern Avraham
Publication year - 2015
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21801
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , discrete mathematics
For given integers k , l we ask whether every large graph with a sufficiently small number of k ‐cliques and k ‐anticliques must contain an induced copy of every l ‐vertex graph. Here we prove this claim for k = l = 3 with a sharp bound. A similar phenomenon is established as well for tournaments with k = l = 4 .
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