Frankl–Rödl graph
id:
frankl-r-dl-graph-321-2244108
title:
Frankl–Rödl graph
text:
In graph theory and computational complexity theory, a Frankl–Rödl graph is a graph defined by connecting pairs of vertices of a hypercube that are at a specified even distance from each other. The graphs of this type are parameterized by the dimension of the hypercube and by the distance between adjacent vertices. Frankl–Rödl graphs are named after Péter Frankl and Vojtěch Rödl, who proved in 1987 that they have small independence number and high chromatic number. They have since become of inte
brand slug:
wiki
category slug:
encyclopedia
description:
Graph used in computational complexity theory and graph theory
original url:
https://en.wikipedia.org/wiki/Frankl%E2%80%93R%C3%B6dl_graph
date created:
date modified:
2024-04-03T14:11:32Z
main entity:
{"identifier":"Q25304863","url":"https://www.wikidata.org/entity/Q25304863"}
image:
{"content_url":"https://upload.wikimedia.org/wikipedia/commons/7/79/Compound_of_two_tetrahedra.png","width":1000,"height":1000}
fields total:
13
integrity:
15