Homomorphism-homogeneous L-colored graphs

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F14%3A10190327" target="_blank" >RIV/00216208:11320/14:10190327 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1016/j.ejc.2013.06.038" target="_blank" >http://dx.doi.org/10.1016/j.ejc.2013.06.038</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ejc.2013.06.038" target="_blank" >10.1016/j.ejc.2013.06.038</a>

Result language

angličtina

Original language name

Homomorphism-homogeneous L-colored graphs

Original language description

A relational structure is homomorphism-homogeneous (HH-homogeneous for short) if every homomorphism between finite induced substructures of the structure can be extended to a homomorphism over the whole domain of the structure. Similarly, a structure ismonomorphism-homogeneous (MH-homogeneous for short) if every monomorphism between finite induced substructures of the structure can be extended to a homomorphism over the whole domain of the structure. In this paper we consider L-colored graphs, that is,undirected graphs without loops where sets of colors selected from L are assigned to vertices and edges. A full classification of finite MH-homogeneous L-colored graphs where L is a chain is provided, and we show that the classes MH and HH coincide. When L is a diamond, that is, a set of pairwise incomparable elements enriched with a greatest and a least element, the situation turns out to be much more involved. We show that in the general case the classes MH and HH do not coincide.

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2014

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

European Journal of Combinatorics

ISSN

0195-6698

e-ISSN

—

Volume of the periodical

35

Issue of the periodical within the volume

January

Country of publishing house

GB - UNITED KINGDOM

Number of pages

11

Pages from-to

313-323

UT code for WoS article

000324786900026

EID of the result in the Scopus database

—