Block circulant graphs and the graphs of critical pairs of crowns

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

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.


Keywords


circulant matrix, order dimension, bipartite poset, chromatic number

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2019.7.2.1

References

B. Codenotti, I. Gerace, and S. Vigna, Hardness results and spectral techniques for combinatorial problems on circulant graphs, Linear Algebra Appl. 285 (1-3) (1998), 123--142.

R. Diestel, Graph theory, Fourth edition, Graduate Texts in Mathematics, 173, Springer, Heidelberg, (2010), ISBN: 978-3-642-14278-9.

M. Discepoli, I. Gerace, R. Mariani, and A. Remigi, A spectral technique to solve the chromatic number problem in circulant graphs, Computational science and its applications--ICCSA 2004 Part III, Lecture Notes in Comput. Sci. 3045, Springer, Berlin, (2004), 745--754.

S. Felsner and W.T. Trotter, Dimension, graph and hypergraph coloring, Order 17 (2) (2000), 167--177.

W.T. Trotter, Combinatorics and partially ordered sets, Johns Hopkins Series in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, (1992), Dimension theory.

W.T. Trotter, Dimension of the crown $mathbb{S}^k_n$, Discrete Math. 8 (1974), 85--103.

W.T. Trotter, Partially ordered sets, Handbook of combinatorics, Vol 1, 2, Elsevier Sci. B. V., Amsterdam, (1995), 433--480.

J.Yanez and J.Montero, A Poset Dimension Algorithm, Journal of Algorithms 30 (1) (1999), 185--208.

J.W.T. Youngs, The Heawood map coloring conjecture, Graph Theory and Theoretical Physics, Academic Press, London, (1967), 313--354.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats