Geodesic
Colouring polytopic partitions in $\mathbb{R}^d$
Mathematica Bohemica, Tome 127 (2002) no. 2, pp. 251-264

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
We consider face-to-face partitions of bounded polytopes into convex polytopes in $\mathbb{R}^d$ for arbitrary $d\ge 1$ and examine their colourability. In particular, we prove that the chromatic number of any simplicial partition does not exceed $d+1$. Partitions of polyhedra in $\mathbb{R}^3$ into pentahedra and hexahedra are $5$- and $6$-colourable, respectively. We show that the above numbers are attainable, i.e., in general, they cannot be reduced.
We consider face-to-face partitions of bounded polytopes into convex polytopes in $\mathbb{R}^d$ for arbitrary $d\ge 1$ and examine their colourability. In particular, we prove that the chromatic number of any simplicial partition does not exceed $d+1$. Partitions of polyhedra in $\mathbb{R}^3$ into pentahedra and hexahedra are $5$- and $6$-colourable, respectively. We show that the above numbers are attainable, i.e., in general, they cannot be reduced.
DOI : 10.21136/MB.2002.134161
Classification : 05C15, 51M20, 65N30
Keywords: colouring multidimensional maps; four colour theorem; chromatic number; tetrahedralization; convex polytopes; finite element methods; domain decomposition methods; parallel programming; combinatorial geometry; six colour conjecture 
Křížek, Michal. Colouring polytopic partitions in $\mathbb{R}^d$. Mathematica Bohemica, Tome 127 (2002) no. 2, pp. 251-264. doi: 10.21136/MB.2002.134161
@article{10_21136_MB_2002_134161,
     author = {K\v{r}{\'\i}\v{z}ek, Michal},
     title = {Colouring polytopic partitions in $\mathbb{R}^d$},
     journal = {Mathematica Bohemica},
     pages = {251--264},
     year = {2002},
     volume = {127},
     number = {2},
     doi = {10.21136/MB.2002.134161},
     mrnumber = {1981530},
     zbl = {1003.05042},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2002.134161/}
}
TY  - JOUR
AU  - Křížek, Michal
TI  - Colouring polytopic partitions in $\mathbb{R}^d$
JO  - Mathematica Bohemica
PY  - 2002
SP  - 251
EP  - 264
VL  - 127
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2002.134161/
DO  - 10.21136/MB.2002.134161
LA  - en
ID  - 10_21136_MB_2002_134161
ER  - 
%0 Journal Article
%A Křížek, Michal
%T Colouring polytopic partitions in $\mathbb{R}^d$
%J Mathematica Bohemica
%D 2002
%P 251-264
%V 127
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2002.134161/
%R 10.21136/MB.2002.134161
%G en
%F 10_21136_MB_2002_134161

[1] K. Appel, W. Haken: Every planar map is four colorable. Bull. Amer. Math. Soc. 82 (1976), 711–712. | DOI | MR

[2] K. Appel, W. Haken: Every planar map is four colorable. I. Discharging. Illinois J. Math. 21 (1977), 429–490. | DOI | MR

[3] K. Appel, W. Haken, J. Koch: Every planar map is four colorable. II. Reducibility. Illinois J. Math. 21 (1977), 491–567. | DOI | MR

[4] R. E. Bank: PLTMG: A Software Package for Solving Partial Differential Equations: Users’ Guide 7.0. SIAM, Philadelphia, 1994. | MR

[5] D. W. Barnette: Coloring polyhedral manifolds. Proc. Conf. Discrete Geometry and Convexity, Ann. N. Y. Acad. Sci. 440 (1985), 192–195. | MR | Zbl

[6] J. H. Brandts: Superconvergence and a posteriori error estimation for triangular mixed finite elements. Numer. Math. 68 (1994), 311–324. | DOI | MR | Zbl

[7] R. Fritsch, G. Fritsch: The Four-Color Theorem. Springer, Berlin, 1998. | MR

[8] J. L. Gross, T. W. Tucker: Topological Graph Theory. John Wiley & Sons, New York, 1987. | MR

[9] B. Grünbaum: Grötzch’s theorem on 3-coloring. Michigan Math. J. 10 (1963), 303–310. | DOI | MR

[10] F. Harary: Graph Theory. Addison-Wesley, London, 1972. | MR

[11] P. J. Heawood: Map colour theorems. Quart. J. Math. 24 (1890), 332–338.

[12] M. Křížek: An equilibrium finite element method in three-dimensional elasticity. Apl. Mat. 27 (1982), 46–75. | MR

[13] M. Křížek, P. Neittaanmäki: Finite Element Approximation of Variational Problems and Applications. Pitman Monographs and Surveys in Pure and Applied Mathematics vol. 50, Longman Scientific & Technical, Harlow, 1990. | MR

[14] M. Křížek, P. Neittaanmäki, R. Stenberg (eds.): Finite Element Methods: Superconvergence, Postprocessing, and A Posteriori Estimates. Proc. Conf., Jyväskylä, 1996, LN in Pure and Appl. Math. vol. 196, Marcel Dekker, New York, 1998. | MR

[15] K. Kuratowski: Sur le problème des courbes gauches en topologie. Fund. Math. 15 (1930), 217–283.

[16] L. Lovász: Three short proofs in graph theory. J. Combin. Theory Ser. B 19 (1975), 269–271. | DOI | MR

[17] J. Mayer: Le problème des régions voisines sur les surfaces closes orientables. J. Comb. Theory Ser. B 6 (1969), 177–195. | DOI | MR | Zbl

[18] G. Ringel: Map Color Theorem. Springer, Berlin, 1974. | MR | Zbl

[19] G. Ringel, J. W. T. Youngs: Solution of the Heawood map-coloring problem. Proc. Natl. Acad. Sci. USA 60 (1968), 438–445. | DOI | MR

[20] N. Robertson, D. P. Sanders, P. D. Seymour, R. Thomas: The four color theorem. J. Combin. Theory Ser. B 70 (1997), 2–44. | DOI | MR

[21] F. Rubin: An improved algorithm for testing the planarity of a graph. IEEE Trans. Comput. c-24 (1975), 113–121. | MR | Zbl

[22] E. Schutle: Tilings. Handbook of Convex Geometry (Gruber P. M. , Will, J. M., eds.), Vol. B, North-Holland, Amsterdam, 1993. | MR

[23] O. Shishkina: Three-colour parallel multilevel preconditioner. Syst. Anal. Modelling Simulation 24 (1996), 255–261. | Zbl

[24] W. T. Tutte: Graph Theory. Addison-Wesley, London, 1984. | MR | Zbl

Cité par Sources :