| dbo:abstract
|
- In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. It is named for Paul Erdős and András Hajnal. More precisely, for an arbitrary undirected graph , let be the family of graphs that do not have as an induced subgraph. Then, according to the conjecture, there exists a constant such that the -vertex graphs in have either a clique or an independent set of size . An equivalent statement to the original conjecture is that, for every graph , the -free graphs all contain polynomially large perfect induced subgraphs. (en)
- En théorie des graphes, la conjecture d'Erdős-Hajnal concerne une relation entre les sous-graphes induits et les cliques et stables. (fr)
- Гипотеза Эрдёша — Хайналя утверждает, что семейства графов, определяемые запрещёнными порождёнными подграфами, имеют либо большие клики, либо большие независимые множества.Точнее, для произвольного неориентированного графа пусть является семейством графов, не содержащих в качестве порождённого подграфа. Тогда, согласно гипотезе, существует константа такая, что графы с вершинами в имеют либо клику, либо независимое множество размером . Эквивалентное утверждение исходной гипотезы: для любого графа не содержащие графы содержат произвольно большие совершенные порождённые подграфы. (ru)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 9371 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- En théorie des graphes, la conjecture d'Erdős-Hajnal concerne une relation entre les sous-graphes induits et les cliques et stables. (fr)
- Гипотеза Эрдёша — Хайналя утверждает, что семейства графов, определяемые запрещёнными порождёнными подграфами, имеют либо большие клики, либо большие независимые множества.Точнее, для произвольного неориентированного графа пусть является семейством графов, не содержащих в качестве порождённого подграфа. Тогда, согласно гипотезе, существует константа такая, что графы с вершинами в имеют либо клику, либо независимое множество размером . Эквивалентное утверждение исходной гипотезы: для любого графа не содержащие графы содержат произвольно большие совершенные порождённые подграфы. (ru)
- In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. It is named for Paul Erdős and András Hajnal. More precisely, for an arbitrary undirected graph , let be the family of graphs that do not have as an induced subgraph. Then, according to the conjecture, there exists a constant such that the -vertex graphs in have either a clique or an independent set of size . (en)
|
| rdfs:label
|
- Erdős–Hajnal conjecture (en)
- Conjecture d'Erdős-Hajnal (fr)
- Гипотеза Эрдёша — Хайналя (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
