Countable ultrahomogeneous 2-colored graphs consisting of disjoint unions of cliques

EUROCOMB’23

Abstract
We classify the countable ultrahomogeneous $2$-vertex-colored graphs in which the color classes form disjoint unions of cliques. This generalizes work by Jenkinson et. al. \cite{JEN12}, Lockett and Truss \cite{LOC14} as well as Rose \cite{ROS11} on ultrahomogeneous $n$-graphs. As the key aspect in such a classification, we identify a concept called piecewise ultrahomogeneity. We prove that there are two specific graphs whose occurrence essentially dictates whether a graph is piecewise ultrahomogeneous, and we exploit this fact to prove the classification.

Pages:
223–230
References

P. J. Cameron. Homogeneous permutations. Electron. J. Combin., 9(2), 2002.
https://doi.org/10.37236/1674

G. Cherlin. The classification of countable homogeneous directed graphs and countable n-tournaments, volume 621 of Mem. Amer. Math. Soc. Amer. Math. Soc., Providence, 1998.
https://doi.org/10.1090/memo/0621

A. Gardiner. Homogeneous graphs. J. Comb. Theory, Ser. B, 20(1):94-102, 1976.
https://doi.org/10.1016/0095-8956(76)90072-1

Y. Golfand and M. Klin. On k-regular graphs. Algorithmic Research in Combinatorics, 186:76-85, 1978.

I. Heinrich, T. Schneider, and P. Schweitzer. Classification of finite highly regular vertex-coloured graphs. https://arxiv.org/abs/2012.01058.

W. Hodges. Model Theory, volume 42 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1993.

T. Jenkinson. The construction and classification of homogeneous structures in model theory. Dissertation, University of Leeds, 2006.

T. Jenkinson, J. K. Truss, and D. Seidel. Countable homogeneous multipartite graphs. Europ. J. Combin., 33(1):82-109, 2012.
https://doi.org/10.1016/j.ejc.2011.04.004

A. H. Lachlan. Countable homogeneous tournaments. Trans. Amer. Math. Soc., 284:431-461, 1984.
https://doi.org/10.1090/S0002-9947-1984-0743728-1

A. H. Lachlan and R. E. Woodrow. Countable ultrahomogeneous undirected graphs. Trans. Amer. Math. Soc., 262:51-94.
https://doi.org/10.1090/S0002-9947-1980-0583847-2

D. C. Lockett and J. K. Truss. Homogeneous coloured multipartite graphs. Europ. J. Comb., 42:217-242, 2014.
https://doi.org/10.1016/j.ejc.2014.06.006

D. Macpherson. A survey of homogeneous structures. Discrete Mathematics, 311(15):1599-1634, 2011.
https://doi.org/10.1016/j.disc.2011.01.024

S. E. Rose. Classification of countable homogeneous 2-graphs. Dissertation, University of Leeds, 2011.

J. H. Schmerl. Countable homogeneous partially ordered sets. Algebra Universalis, 9:317-321, 1979.
https://doi.org/10.1007/BF02488043

J. Sheehan. Smoothly embeddable subgraphs. J. London Math. Soc., s2-9(2):212-218, 1974.
https://doi.org/10.1112/jlms/s2-9.2.212

Metrics

0

Views

0

PDF views