Erdős–Hajnal conjecture (original) (raw)
En théorie des graphes, la conjecture d'Erdős-Hajnal concerne une relation entre les sous-graphes induits et les cliques et stables.
| Property | Value |
|---|---|
| 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 | http://www.openproblemgarden.org/op/the_erdos_hajnal_conjecture |
| dbo:wikiPageID | 42585591 (xsd:integer) |
| dbo:wikiPageLength | 9371 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1117410686 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:András_Hajnal dbr:Paul_Erdős dbr:Paul_Seymour_(mathematician) dbr:Undirected_graph dbr:Independent_set_(graph_theory) dbr:Induced_subgraph dbc:Conjectures dbr:Erdős–Rényi_model dbr:Logarithm dbr:Clique_(graph_theory) dbr:Perfect_graph dbr:Tournament_(graph_theory) dbr:Cycle_graph dbr:Forbidden_graph_characterization dbr:Graph_theory dbc:Ramsey_theory dbc:Unsolved_problems_in_graph_theory dbr:Cograph dbr:Modular_decomposition dbr:Maria_Chudnovsky dbc:Paul_Erdős dbr:Ramsey's_theorem dbr:Maximum_clique dbr:Random_graph dbr:Maximum_independent_set |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Short_description dbt:Unsolved |
| dcterms:subject | dbc:Conjectures dbc:Ramsey_theory dbc:Unsolved_problems_in_graph_theory dbc:Paul_Erdős |
| rdf:type | yago:WikicatConjectures yago:Abstraction100002137 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Hypothesis105888929 yago:Idea105833840 yago:PsychologicalFeature100023100 yago:Speculation105891783 |
| 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 | freebase:Erdős–Hajnal conjecture wikidata:Erdős–Hajnal conjecture dbpedia-fr:Erdős–Hajnal conjecture dbpedia-ru:Erdős–Hajnal conjecture https://global.dbpedia.org/id/fJ8A |
| prov:wasDerivedFrom | wikipedia-en:Erdős–Hajnal_conjecture?oldid=1117410686&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Erdős–Hajnal_conjecture |
| is dbo:wikiPageRedirects of | dbr:Erdos-Hajnal_conjecture dbr:Erdős-Hajnal_conjecture dbr:Erdos–Hajnal_conjecture |
| is dbo:wikiPageWikiLink of | dbr:List_of_conjectures_by_Paul_Erdős dbr:Paul_Seymour_(mathematician) dbr:Erdos-Hajnal_conjecture dbr:Erdős-Hajnal_conjecture dbr:Forbidden_graph_characterization dbr:Forbidden_subgraph_problem dbr:Erdos–Hajnal_conjecture dbr:Bull_graph dbr:List_of_things_named_after_Paul_Erdős dbr:List_of_unsolved_problems_in_mathematics |
| is foaf:primaryTopic of | wikipedia-en:Erdős–Hajnal_conjecture |