Block circulant graphs and the graphs of critical pairs of crowns

Rebecca E. Garcia, Pamela E. Harris, Bethany Kubik, Shannon Talbott

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper, we provide a natural bijection between a special family of block circulant graphs and the graphs of critical pairs of the posets known as generalized crowns. In particular, every graph in this family of block circulant graphs we investigate has a generating block row that follows a symmetric growth pattern of the all ones matrix. The natural bijection provides an upper bound on the chromatic number for this infinite family of graphs.

Original languageEnglish (US)
Pages (from-to)207-216
Number of pages10
JournalElectronic Journal of Graph Theory and Applications
Volume7
Issue number2
DOIs
StatePublished - 2019

Bibliographical note

Funding Information:
The authors thank Joseph Pedersen for his work on the Mathematica code that provided much insight. The authors acknowledge Charity Bankhead for her initial computational contributions to this project, and thank William T. Trotter for many helpful and enlightening conversations during the completion of this manuscript. As this project began during the 2013 SACNAS National Conference, the authors thank the society for providing an enriching environment that encouraged this scientific collaboration. The authors extend their gratitude to the Center for Leadership and Diversity in STEM at the United States Military Academy, the National Science Foundation Division of Mathematical Sciences (DMS-1045082), and the AMS-Simons Travel Grant for travel support.

Keywords

  • Bipartite poset
  • Chromatic number
  • Circulant matrix
  • Order dimension

Fingerprint Dive into the research topics of 'Block circulant graphs and the graphs of critical pairs of crowns'. Together they form a unique fingerprint.

Cite this