Characterizing graphs of critical pairs of layered generalized crowns. Issue 1 (2nd January 2020)

• Record Type: Journal Article
• Authors: Garcia, Rebecca E.; Harris, Pamela E.; Kubik, Bethany; Talbott, Shannon
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 17:Issue 1(2020)
• Page Start: 387
• Page End: 401
• Publication Date: 2020-01-02
• Subjects: Order dimension -- Multipartite poset -- Chromatic number
• DOI: 10.1016/j.akcej.2019.03.001
• Languages: English
• ISSNs: 0972-8600

Abstract

Abstract: The generalized crown S n k is a well-known family of bipartite graphs whose order dimension is given in terms of the parameters n and k . In recent work, Garcia and Silva defined the notion of layering generalized crowns, producing multipartite posets called ℓ -layered generalized crowns, whose order dimension is easily determined using ℓ, n, and k . 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 ℓ -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.