Statements (25)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
graph
|
| gptkbp:application |
proving upper bounds in extremal graph theory
|
| gptkbp:chromaticNumber |
r
|
| gptkbp:cliqueNumber |
r
|
| gptkbp:definedIn |
two parameters n and r
|
| gptkbp:edgeCount |
floor((1-1/r) * n^2 / 2)
|
| gptkbp:field |
graph theory
|
| gptkbp:generalizes |
complete bipartite graph (for r=2)
complete graph (for r=n) |
| gptkbp:hasNo |
(r+1)-clique
|
| gptkbp:heldBy |
unique (up to isomorphism) for given n and r
|
| https://www.w3.org/2000/01/rdf-schema#label |
Turán graph
|
| gptkbp:namedAfter |
gptkb:Pál_Turán
|
| gptkbp:notation |
T(n, r)
|
| gptkbp:property |
complete r-partite graph with parts as equal as possible
maximizes number of edges among n-vertex graphs with no (r+1)-clique |
| gptkbp:relatedTo |
gptkb:Erdős–Stone_theorem
gptkb:Turán's_theorem |
| gptkbp:type |
extremal graph
|
| gptkbp:usedIn |
extremal combinatorics
|
| gptkbp:bfsParent |
gptkb:Pál_Turán
gptkb:Paul_Turán gptkb:Turán's_theorem gptkb:fundamental_theorem_of_extremal_graph_theory |
| gptkbp:bfsLayer |
6
|