About: De Bruijn–Erdős theorem (graph theory)

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: De Bruijn–Erdős theorem (graph theory) Goto Sponge NotDistinct Permalink

An Entity of Type : yago:VisualCommunication106873252, within Data Space : dbpedia.org:8891 associated with source document(s)
QRcode icon

http://dbpedia.org:8891/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FDe_Bruijn%E2%80%93Erd%C5%91s_theorem_%28graph_theory%29

In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős, after whom it is named.

Attributes	Values
rdf:type	yago:WikicatTheoremsInGraphTheory yago:Abstraction100002137 yago:Communication100033020 yago:Graph107000195 yago:Message106598915 yago:Proposition106750804 yago:WikicatInfiniteGraphs yago:Statement106722453 yago:Theorem106752293 yago:VisualCommunication106873252
rdfs:label	Teorema de De Bruijn–Erdős (teoria de grafs) (ca) De Bruijn–Erdős theorem (graph theory) (en) Théorème de De Bruijn-Erdős (théorie des graphes) (fr) Теорема де Брёйна — Эрдёша (теория графов) (ru) Теорема де Брейна — Ердеша (теорія графів) (uk)
rdfs:comment	En teoria de grafs, el teorema de De Bruijn-Erdős, demostrat per Nicolaas Govert de Bruijn i Paul Erdős el 1951, estableix que, per a cada G i enter finit k, es pot acolorir G amb k colors (de manera que cap parell de vèrtexs adjacents tingui el mateix color) si i només si tots els seus subgrafs finits es poden acolorir amb k colors. És a dir, cada (és a dir, cada graf que requereix k colors però per al qual tots els subgrafs requereixen un nombre menor de colors) ha de tenir un nombre finit de vèrtexs. (ca) Le théorème de De Bruijn-Erdős en théorie des graphes, démontré par Nicolaas Govert de Bruijn et Paul Erdős, établit que (pour tout entier naturel k) pour qu'un graphe non orienté infini possède une coloration par k couleurs, il suffit qu'il en soit ainsi pour tous ses sous-graphes finis. Autrement dit : tout graphe (en) (i.e. dont toute coloration a au moins k couleurs mais dont tous les sous-graphes propres sont k – 1-colorables) a un nombre fini de sommets. (fr) Теорема де Брёйна — Эрдёша — классическая теорема теории графов доказанная Палом Эрдёшем и Николаасом де Брёйном. (ru) Теорема де Брейна — Ердеша — класична теорема теорії графів доведена Палом Ердешем і Ніколасом де Брейном. (uk) In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős, after whom it is named. (en)
foaf:depiction
dcterms:subject	Axiom of choice Graph coloring Infinite graphs Theorems in graph theory Paul Erdős
Wikipage page ID	22728378 (xsd:integer)
Wikipage revision ID	1110834781 (xsd:integer)
Link from a Wikipage to another Wikipage	Axiom of choice Model theory Moser spindle Andrey Nikolayevich Tychonoff Binary relation Bethe lattice Paul Erdős Undirected graph Unit distance graph Upper bound Indagationes Mathematicae Induced subgraph Kőnig's lemma Transfinite induction Notre Dame Journal of Formal Logic Solovay model Graph coloring Compact space Orientation (graph theory) Chromatic number Gabriel Andrew Dirac Generalized continuum hypothesis Glossary of graph theory Graph coloring Infinite graphs Subgraph (graph theory) Closed set Compactness theorem Comparability graph Hadwiger–Nelson problem Proceedings of the American Mathematical Society Structure (mathematical logic) Total order Undefined (mathematics) Lajos Pósa (mathematician) Logical Methods in Computer Science Edge (graph theory) Equivalence relation Finite intersection property Finite set Four-color theorem Nicolaas Govert de Bruijn Non-standard analysis Partially ordered set Cardinal number Cardinality Dilworth's theorem Discrete Mathematics (journal) Graph theory Israel Journal of Mathematics Journal of Combinatorial Theory First-order predicate calculus Ultrafilter Quanta Magazine Theorems in graph theory Acta Mathematica Academiae Scientiarum Hungaricae Hypergraph Bipartite graph Zorn's lemma Axiom of choice Boolean prime ideal theorem Paul Erdős Infinite graph Kurt Gödel Canadian Journal of Mathematics Rational number Mathematical Association of America Maximal element Second-order arithmetic Tychonoff's theorem Vertex (graph theory) Euclidean distance

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3331 as of Sep 2 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (62 GB total memory, 40 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software