Characterizing graphs of critical pairs of layered generalized crowns

Abstract

The generalized crown is a well-known family of bipartite graphs whose order dimension is given in terms of the parameters and . 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 , , and . 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.

Keywords

• order dimension
• multipartite poset
• chromatic number