Matches in DBpedia 2016-04 for { ?s ?p "In graph theory, the Heawood conjecture or Ringel–Youngs theorem gives a lower bound for the number of colors that are necessary for graph coloring on a surface of a given genus. For surfaces of genus 0, 1, 2, 3, 4, 5, 6, 7, ..., the required number of colors is 4, 7, 8, 9, 10, 11, 12, 12, .... OEIS A000934, the chromatic number or Heawood number.The conjecture was formulated in 1890 by Percy John Heawood and proven in 1968 by Gerhard Ringel and Ted Youngs. One case, the non-orientable Klein bottle, proved an exception to the general formula. An entirely different approach was needed for the much older problem of finding the number of colors needed for the plane or sphere, solved in 1976 as the four color theorem by Haken and Appel. On the sphere the lower bound is easy, whereas for higher genera the upper bound is easy and was proved in Heawood's original short paper that contained the conjecture. In other words, Ringel, Youngs and others had to construct extreme examples for every genus g = 1,2,3,.... If g = 12s + k, the genera fall into 12 cases according as k = 0,1,2,3,4,5,6,7,8,9,10,11. To simplify, suppose that case k has been established if only a finite number of g's of the form 12s + k are in doubt. Then the years in which the twelve cases were settled and by whom are the following:1954, Ringel: case 51961, Ringel: cases 3,7,101963, Terry, Welch, Youngs: cases 0,41964, Gustin, Youngs: case 11965, Gustin: case 91966, Youngs: case 61967, Ringel, Youngs: cases 2,8,11The last seven sporadic exceptions were settled as follows:1967, Mayer: cases 18, 20, 231968, Ringel, Youngs: cases 30, 35, 47, 59, and the conjecture was proved."@en }
Showing triples 1 to 2 of
2
with 100 triples per page.
- Heawood_conjecture abstract "In graph theory, the Heawood conjecture or Ringel–Youngs theorem gives a lower bound for the number of colors that are necessary for graph coloring on a surface of a given genus. For surfaces of genus 0, 1, 2, 3, 4, 5, 6, 7, ..., the required number of colors is 4, 7, 8, 9, 10, 11, 12, 12, .... OEIS A000934, the chromatic number or Heawood number.The conjecture was formulated in 1890 by Percy John Heawood and proven in 1968 by Gerhard Ringel and Ted Youngs. One case, the non-orientable Klein bottle, proved an exception to the general formula. An entirely different approach was needed for the much older problem of finding the number of colors needed for the plane or sphere, solved in 1976 as the four color theorem by Haken and Appel. On the sphere the lower bound is easy, whereas for higher genera the upper bound is easy and was proved in Heawood's original short paper that contained the conjecture. In other words, Ringel, Youngs and others had to construct extreme examples for every genus g = 1,2,3,.... If g = 12s + k, the genera fall into 12 cases according as k = 0,1,2,3,4,5,6,7,8,9,10,11. To simplify, suppose that case k has been established if only a finite number of g's of the form 12s + k are in doubt. Then the years in which the twelve cases were settled and by whom are the following:1954, Ringel: case 51961, Ringel: cases 3,7,101963, Terry, Welch, Youngs: cases 0,41964, Gustin, Youngs: case 11965, Gustin: case 91966, Youngs: case 61967, Ringel, Youngs: cases 2,8,11The last seven sporadic exceptions were settled as follows:1967, Mayer: cases 18, 20, 231968, Ringel, Youngs: cases 30, 35, 47, 59, and the conjecture was proved.".
- Q2799491 abstract "In graph theory, the Heawood conjecture or Ringel–Youngs theorem gives a lower bound for the number of colors that are necessary for graph coloring on a surface of a given genus. For surfaces of genus 0, 1, 2, 3, 4, 5, 6, 7, ..., the required number of colors is 4, 7, 8, 9, 10, 11, 12, 12, .... OEIS A000934, the chromatic number or Heawood number.The conjecture was formulated in 1890 by Percy John Heawood and proven in 1968 by Gerhard Ringel and Ted Youngs. One case, the non-orientable Klein bottle, proved an exception to the general formula. An entirely different approach was needed for the much older problem of finding the number of colors needed for the plane or sphere, solved in 1976 as the four color theorem by Haken and Appel. On the sphere the lower bound is easy, whereas for higher genera the upper bound is easy and was proved in Heawood's original short paper that contained the conjecture. In other words, Ringel, Youngs and others had to construct extreme examples for every genus g = 1,2,3,.... If g = 12s + k, the genera fall into 12 cases according as k = 0,1,2,3,4,5,6,7,8,9,10,11. To simplify, suppose that case k has been established if only a finite number of g's of the form 12s + k are in doubt. Then the years in which the twelve cases were settled and by whom are the following:1954, Ringel: case 51961, Ringel: cases 3,7,101963, Terry, Welch, Youngs: cases 0,41964, Gustin, Youngs: case 11965, Gustin: case 91966, Youngs: case 61967, Ringel, Youngs: cases 2,8,11The last seven sporadic exceptions were settled as follows:1967, Mayer: cases 18, 20, 231968, Ringel, Youngs: cases 30, 35, 47, 59, and the conjecture was proved.".