Colouring polytopic partitions in ℝ d

Michal Křížek

Mathematica Bohemica (2002)

  • Volume: 127, Issue: 2, page 251-264
  • ISSN: 0862-7959

Abstract

top
We consider face-to-face partitions of bounded polytopes into convex polytopes in ℝ d for arbitrary d ≥ 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 ℝ 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.

How to cite

top

Křížek, Michal. "Colouring polytopic partitions in $\mathbb {R}^d$." Mathematica Bohemica 127.2 (2002): 251-264. <http://eudml.org/doc/249039>.

@article{Křížek2002,
abstract = {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.},
author = {Křížek, Michal},
journal = {Mathematica Bohemica},
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; colouring multidimensional maps; four colour theorem; chromatic number; tetrahedralization; convex polytopes; finite element methods; domain decomposition methods; parallel programming; combinatorial geometry; six colour conjecture},
language = {eng},
number = {2},
pages = {251-264},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Colouring polytopic partitions in $\mathbb \{R\}^d$},
url = {http://eudml.org/doc/249039},
volume = {127},
year = {2002},
}

TY - JOUR
AU - Křížek, Michal
TI - Colouring polytopic partitions in $\mathbb {R}^d$
JO - Mathematica Bohemica
PY - 2002
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 127
IS - 2
SP - 251
EP - 264
AB - 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.
LA - eng
KW - colouring multidimensional maps; four colour theorem; chromatic number; tetrahedralization; convex polytopes; finite element methods; domain decomposition methods; parallel programming; combinatorial geometry; six colour conjecture; colouring multidimensional maps; four colour theorem; chromatic number; tetrahedralization; convex polytopes; finite element methods; domain decomposition methods; parallel programming; combinatorial geometry; six colour conjecture
UR - http://eudml.org/doc/249039
ER -

References

top
  1. 10.1090/S0002-9904-1976-14122-5, Bull. Amer. Math. Soc. 82 (1976), 711–712. (1976) MR0424602DOI10.1090/S0002-9904-1976-14122-5
  2. 10.1215/ijm/1256049011, Illinois J. Math. 21 (1977), 429–490. (1977) MR0543792DOI10.1215/ijm/1256049011
  3. 10.1215/ijm/1256049012, Illinois J. Math. 21 (1977), 491–567. (1977) MR0543793DOI10.1215/ijm/1256049012
  4. PLTMG: A Software Package for Solving Partial Differential Equations: Users’ Guide 7.0, SIAM, Philadelphia, 1994. (1994) MR1262123
  5. Coloring polyhedral manifolds, Proc. Conf. Discrete Geometry and Convexity, Ann. N. Y. Acad. Sci. 440 (1985), 192–195. (1985) Zbl0571.05018MR0809206
  6. 10.1007/s002110050064, Numer. Math. 68 (1994), 311–324. (1994) Zbl0823.65103MR1313147DOI10.1007/s002110050064
  7. The Four-Color Theorem, Springer, Berlin, 1998. (1998) MR1633950
  8. Topological Graph Theory, John Wiley & Sons, New York, 1987. (1987) MR0898434
  9. 10.1307/mmj/1028998916, Michigan Math. J. 10 (1963), 303–310. (1963) MR0154274DOI10.1307/mmj/1028998916
  10. Graph Theory, Addison-Wesley, London, 1972. (1972) MR0256911
  11. Map colour theorems, Quart. J. Math. 24 (1890), 332–338. (1890) 
  12. An equilibrium finite element method in three-dimensional elasticity, Apl. Mat. 27 (1982), 46–75. (1982) MR0640139
  13. Finite Element Approximation of Variational Problems and Applications, Pitman Monographs and Surveys in Pure and Applied Mathematics vol. 50, Longman Scientific & Technical, Harlow, 1990. (1990) MR1066462
  14. 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. (1998) MR1602809
  15. Sur le problème des courbes gauches en topologie, Fund. Math. 15 (1930), 217–283. (1930) 
  16. 10.1016/0095-8956(75)90089-1, J. Combin. Theory Ser. B 19 (1975), 269–271. (1975) MR0396344DOI10.1016/0095-8956(75)90089-1
  17. 10.1016/S0021-9800(69)80118-3, J. Comb. Theory Ser. B 6 (1969), 177–195. (1969) Zbl0182.26601MR0234863DOI10.1016/S0021-9800(69)80118-3
  18. Map Color Theorem, Springer, Berlin, 1974. (1974) Zbl0287.05102MR0349461
  19. 10.1073/pnas.60.2.438, Proc. Natl. Acad. Sci. USA 60 (1968), 438–445. (1968) MR0228378DOI10.1073/pnas.60.2.438
  20. 10.1006/jctb.1997.1750, J. Combin. Theory Ser. B 70 (1997), 2–44. (1997) MR1441258DOI10.1006/jctb.1997.1750
  21. An improved algorithm for testing the planarity of a graph, IEEE Trans. Comput. c-24 (1975), 113–121. (1975) Zbl0297.68030MR0414407
  22. Tilings, Handbook of Convex Geometry (Gruber P. M. , Will, J. M., eds.), Vol. B, North-Holland, Amsterdam, 1993. (1993) MR1242973
  23. Three-colour parallel multilevel preconditioner, Syst. Anal. Modelling Simulation 24 (1996), 255–261. (1996) Zbl0935.65045
  24. Graph Theory, Addison-Wesley, London, 1984. (1984) Zbl0554.05001MR0746795

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.