| Title:
|
Colouring polytopic partitions in $\mathbb{R}^d$ (English) |
| Author:
|
Křížek, Michal |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
127 |
| Issue:
|
2 |
| Year:
|
2002 |
| Pages:
|
251-264 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
colouring multidimensional maps |
| Keyword:
|
four colour theorem |
| Keyword:
|
chromatic number |
| Keyword:
|
tetrahedralization |
| Keyword:
|
convex polytopes |
| Keyword:
|
finite element methods |
| Keyword:
|
domain decomposition methods |
| Keyword:
|
parallel programming |
| Keyword:
|
combinatorial geometry |
| Keyword:
|
six colour conjecture |
| MSC:
|
05C15 |
| MSC:
|
51M20 |
| MSC:
|
65N30 |
| idZBL:
|
Zbl 1003.05042 |
| idMR:
|
MR1981530 |
| DOI:
|
10.21136/MB.2002.134161 |
| . |
| Date available:
|
2012-10-05T12:59:47Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/134161 |
| . |
| Reference:
|
[1] K. Appel, W. Haken: Every planar map is four colorable.Bull. Amer. Math. Soc. 82 (1976), 711–712. MR 0424602, 10.1090/S0002-9904-1976-14122-5 |
| Reference:
|
[2] K. Appel, W. Haken: Every planar map is four colorable. I. Discharging.Illinois J. Math. 21 (1977), 429–490. MR 0543792, 10.1215/ijm/1256049011 |
| Reference:
|
[3] K. Appel, W. Haken, J. Koch: Every planar map is four colorable. II. Reducibility.Illinois J. Math. 21 (1977), 491–567. MR 0543793, 10.1215/ijm/1256049012 |
| Reference:
|
[4] R. E. Bank: PLTMG: A Software Package for Solving Partial Differential Equations: Users’ Guide 7.0.SIAM, Philadelphia, 1994. MR 1262123 |
| Reference:
|
[5] D. W. Barnette: Coloring polyhedral manifolds.Proc. Conf. Discrete Geometry and Convexity, Ann. N. Y. Acad. Sci. 440 (1985), 192–195. Zbl 0571.05018, MR 0809206 |
| Reference:
|
[6] J. H. Brandts: Superconvergence and a posteriori error estimation for triangular mixed finite elements.Numer. Math. 68 (1994), 311–324. Zbl 0823.65103, MR 1313147, 10.1007/s002110050064 |
| Reference:
|
[7] R. Fritsch, G. Fritsch: The Four-Color Theorem.Springer, Berlin, 1998. MR 1633950 |
| Reference:
|
[8] J. L. Gross, T. W. Tucker: Topological Graph Theory.John Wiley & Sons, New York, 1987. MR 0898434 |
| Reference:
|
[9] B. Grünbaum: Grötzch’s theorem on 3-coloring.Michigan Math. J. 10 (1963), 303–310. MR 0154274, 10.1307/mmj/1028998916 |
| Reference:
|
[10] F. Harary: Graph Theory.Addison-Wesley, London, 1972. MR 0256911 |
| Reference:
|
[11] P. J. Heawood: Map colour theorems.Quart. J. Math. 24 (1890), 332–338. |
| Reference:
|
[12] M. Křížek: An equilibrium finite element method in three-dimensional elasticity.Apl. Mat. 27 (1982), 46–75. MR 0640139 |
| Reference:
|
[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 1066462 |
| Reference:
|
[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 1602809 |
| Reference:
|
[15] K. Kuratowski: Sur le problème des courbes gauches en topologie.Fund. Math. 15 (1930), 217–283. |
| Reference:
|
[16] L. Lovász: Three short proofs in graph theory.J. Combin. Theory Ser. B 19 (1975), 269–271. MR 0396344, 10.1016/0095-8956(75)90089-1 |
| Reference:
|
[17] J. Mayer: Le problème des régions voisines sur les surfaces closes orientables.J. Comb. Theory Ser. B 6 (1969), 177–195. Zbl 0182.26601, MR 0234863, 10.1016/S0021-9800(69)80118-3 |
| Reference:
|
[18] G. Ringel: Map Color Theorem.Springer, Berlin, 1974. Zbl 0287.05102, MR 0349461 |
| Reference:
|
[19] G. Ringel, J. W. T. Youngs: Solution of the Heawood map-coloring problem.Proc. Natl. Acad. Sci. USA 60 (1968), 438–445. MR 0228378, 10.1073/pnas.60.2.438 |
| Reference:
|
[20] N. Robertson, D. P. Sanders, P. D. Seymour, R. Thomas: The four color theorem.J. Combin. Theory Ser. B 70 (1997), 2–44. MR 1441258, 10.1006/jctb.1997.1750 |
| Reference:
|
[21] F. Rubin: An improved algorithm for testing the planarity of a graph.IEEE Trans. Comput. c-24 (1975), 113–121. Zbl 0297.68030, MR 0414407 |
| Reference:
|
[22] E. Schutle: Tilings.Handbook of Convex Geometry (Gruber P. M. , Will, J. M., eds.), Vol. B, North-Holland, Amsterdam, 1993. MR 1242973 |
| Reference:
|
[23] O. Shishkina: Three-colour parallel multilevel preconditioner.Syst. Anal. Modelling Simulation 24 (1996), 255–261. Zbl 0935.65045 |
| Reference:
|
[24] W. T. Tutte: Graph Theory.Addison-Wesley, London, 1984. Zbl 0554.05001, MR 0746795 |
| . |
