Matches in DBpedia 2016-04 for { ?s ?p "In graph theory, the De Bruijn–Erdős theorem, proved by Nicolaas Govert de Bruijn and Paul Erdős (1951), states that, for every infinite graph G and finite integer k, G can be colored by k colors (with no two adjacent vertices having the same color) if and only if all of its finite subgraphs can be colored by k colors. That is, every k-critical graph (a graph that requires k colors but for which all subgraphs require fewer colors) must have a finite number of vertices.The De Bruijn–Erdős theorem has several different proofs, all depending in some way on the axiom of choice. Its applications include extending the four-color theorem and Dilworth's theorem from finite graphs and partial orders to infinite ones, and reducing the Hadwiger–Nelson problem on the chromatic number of the plane to a problem about finite graphs. It may be generalized from finite numbers of colors to sets of colors whose cardinality is a strongly compact cardinal."@en }
Showing triples 1 to 2 of
2
with 100 triples per page.
- De_Bruijn–Erdős_theorem_(graph_theory) abstract "In graph theory, the De Bruijn–Erdős theorem, proved by Nicolaas Govert de Bruijn and Paul Erdős (1951), states that, for every infinite graph G and finite integer k, G can be colored by k colors (with no two adjacent vertices having the same color) if and only if all of its finite subgraphs can be colored by k colors. That is, every k-critical graph (a graph that requires k colors but for which all subgraphs require fewer colors) must have a finite number of vertices.The De Bruijn–Erdős theorem has several different proofs, all depending in some way on the axiom of choice. Its applications include extending the four-color theorem and Dilworth's theorem from finite graphs and partial orders to infinite ones, and reducing the Hadwiger–Nelson problem on the chromatic number of the plane to a problem about finite graphs. It may be generalized from finite numbers of colors to sets of colors whose cardinality is a strongly compact cardinal.".
- Q3527054 abstract "In graph theory, the De Bruijn–Erdős theorem, proved by Nicolaas Govert de Bruijn and Paul Erdős (1951), states that, for every infinite graph G and finite integer k, G can be colored by k colors (with no two adjacent vertices having the same color) if and only if all of its finite subgraphs can be colored by k colors. That is, every k-critical graph (a graph that requires k colors but for which all subgraphs require fewer colors) must have a finite number of vertices.The De Bruijn–Erdős theorem has several different proofs, all depending in some way on the axiom of choice. Its applications include extending the four-color theorem and Dilworth's theorem from finite graphs and partial orders to infinite ones, and reducing the Hadwiger–Nelson problem on the chromatic number of the plane to a problem about finite graphs. It may be generalized from finite numbers of colors to sets of colors whose cardinality is a strongly compact cardinal.".