Homomorphism-homogeneous L-colored graphs

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Homomorphism-homogeneous L-colored graphs

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Homomorphism-homogeneous L-colored graphs

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

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

Rok uplatnění

2014

Kód důvěrnosti údajů

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

Název periodika

European Journal of Combinatorics

ISSN

0195-6698

e-ISSN

—

Svazek periodika

35

Číslo periodika v rámci svazku

January

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

11

Strana od-do

313-323

Kód UT WoS článku

000324786900026

EID výsledku v databázi Scopus

—