10.1007/s40096-020-00358-1

A new algorithmic method to compute the chromatic number of Dihedral group

Show Details XML
  • Azar Shokri1,
  • Maryam Golriz*1,
  1. Department Mathematics, Islamic Azad University-South Tehran Branch, Tehran, IR

Published in Issue 2021-01-02

How to Cite

Shokri, A., & Golriz, M. (2021). A new algorithmic method to compute the chromatic number of Dihedral group. Mathematical Sciences, 15(2 (June 2021). https://doi.org/10.1007/s40096-020-00358-1
Crossref
Scopus
Google Scholar
Europe PMC

Abstract

Abstract In this paper, we will compute the chromatic number of D9\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$D_9$$\end{document} , D15\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$D_{15}$$\end{document} , and we will present an algorithm to compute the chromatic number of any Latin square of Dn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$D_n$$\end{document} (for all n ) order.

Keywords

  • Latin square,
  • Transversal,
  • Partial transversal,
  • Chromatic number,
  • Complete mapping,
  • Dihedral group

References

  1. Abel, R., Julian, R., Diana, Combe, Nelson, Adrian, M., Palmer, William D.: GBRDs with block size three over 2-groups, semi-dihedral groups and nilpotent groups. Electron. J. Comb. 18(1):Paper 32, 12, (2011)
  2. Besharati et al. (2016) On the chromatic number of Latin square graphs, volume 10486 339(11) (pp. 2613-2619) https://doi.org/10.1016/j.disc.2016.04.025
  3. Mortezaeefar, M.: Colorings of Latin square graphs and block designs. Master’s thesis, Sharif University of Technology, Tehran, Iran, (2009) (in Farsi, 23 Persian language)
  4. Shokri, K.: On the Latin square of groups and their coloring, Master’s thesis, Sharif University of Technology, Tehran, Iran, (2015) (in Farsi, 23 Persian language)
  5. Wanless, I.M.: Transversals in Latin squares: a survey. In: Surveys in Combinatorics 2011, London Math. Soc. Lecture Note Ser., vol. 392, pp. 403–437. Cambridge University Press, Cambridge (2011)