Morphism extension classes of countable $L$-colored graphs

Abstract

In~\cite{Hartman:2014}, Hartman, Hubi\v cka and Ma\v sulović studied the hierarchy of morphism extension classes for finite $L$-colored graphs, that is, undirected graphs without loops where sets of colors selected from $L$ are assigned to vertices and edges. They proved that when $L$ is a linear order, the classes $M{H}_L$ and $H{H}_L$ coincide, and the same is true for vertex-uniform finite $L$-colored graphs when $L$ is a diamond. In this paper, we explore the same question for countably infinite $L$-colored graphs. We prove that $M{H}_L=H{H}_L$ if and only if $L$ is a linear order.

12 pages, 1 figure