Characterizing graphs of critical pairs of layered generalized crowns

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

Research output: Contribution to journalArticlepeer-review

Abstract

The generalized crown (Formula presented.) is a well-known family of bipartite graphs whose order dimension is given in terms of the parameters (Formula presented.) and (Formula presented.). In recent work, Garcia and Silva defined the notion of layering generalized crowns, producing multipartite posets called (Formula presented.) -layered generalized crowns, whose order dimension is easily determined using (Formula presented.), (Formula presented.), and (Formula presented.). This paper extends the authors’ prior work on characterizing the associated graphs of critical pairs of generalized crowns, by providing a new and concrete description of an infinite family of graphs arising from critical pairs of the (Formula presented.) -layered generalized crowns. Our main result gives a characterization of the adjacency matrices of these graphs. Through their associated posets with computable order dimension, these graphs have a strict upper bound on their chromatic number.

Original languageEnglish (US)
Pages (from-to)387-401
Number of pages15
JournalAKCE International Journal of Graphs and Combinatorics
Volume17
Issue number1
DOIs
StatePublished - Jan 2 2020

Bibliographical note

Funding Information:
The authors extend their gratitude to the National Science Foundation Division of Mathematical Sciences (DMS-1045082) for travel support.

Publisher Copyright:
© 2018 Kalasalingam University. Published with license by Taylor & Francis Group, LLC.

Keywords

  • Chromatic number
  • Multipartite poset
  • Order dimension

Fingerprint Dive into the research topics of 'Characterizing graphs of critical pairs of layered generalized crowns'. Together they form a unique fingerprint.

Cite this