Block circulant graphs and the graphs of critical pairs of crowns

DOI10.5614/EJGTA.2019.7.2.1MaRDI QIDQ5009946zbMATH OpenOpenAlexFDO

Authors Pamela E. Harris, Bethany Kubik, Shannon N. Talbott, R. E. Garcia

Publication date 23 August 2021

Published in Electronic Journal of Graph Theory and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution-ShareAlike 4.0 International

Full work available at URL https://arxiv.org/abs/1410.5087

zbMATH Keywords

bipartite posetchromatic numbercirculant matrixorder dimension

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Partial orders, general (06A06) Combinatorics of partially ordered sets (06A07)

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.

Recommendations

• Characterizing graphs of critical pairs of layered generalized crowns
• The graph of critical pairs of a crown
• On planarity and colorability of circulant graphs
• scientific article; zbMATH DE number 22642
• 4-critical 4-valent planar graphs constructed with crowns.

Cites work

• A Poset Dimension Algorithm
• Computational Science and Its Applications – ICCSA 2004
• Dimension of the crown \(S^k_n\)
• Dimension, graph and hypergraph coloring
• Graph theory
• Hardness results and spectral techniques for combinatorial problems on circulant graphs
• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• scientific article; zbMATH DE number 863477 (Why is no real title available?)
• scientific article; zbMATH DE number 3327124 (Why is no real title available?)

Cited in

(3)

• The graph of critical pairs of a crown
• scientific article; zbMATH DE number 3918415 (Why is no real title available?)
• Characterizing graphs of critical pairs of layered generalized crowns

This page was built for publication: Block circulant graphs and the graphs of critical pairs of crowns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5009946)