Morphism extension classes of countable L-colored graphs

Authors: A. Aranda, David Hartman
Publication year: 2026
Publication type: Článek v odborném periodiku
Periodical: European Journal of Combinatorics
Projects: Center of excellence - Institute for theoretical computer science (CE-ITI)
Bibliographic citation: ARANDA, A., HARTMAN, David. Morphism extension classes of countable L-colored graphs. European Journal of Combinatorics. 2026, 132(Part A), 104256. ISSN 0195-6698. E-ISSN 1095-9971
Dostupné z: doi:10.1016/j.ejc.2025.104256.
DOI: 10.1016/j.ejc.2025.104256
ID: 643501
Online record: View online record

Abstract

In Hartman et al. (2014), Hartman, Hubička and Mašulović 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 MHL and HHL coincide, and the same is true for vertex-uniform finite L-colored graphs when is a diamond. In this paper, we explore the same question for countably infinite L-colored graphs. We prove that MHL = HHL if and only if L is a linear order.