On the density of trigraph homomorphisms (Q2373444): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Q790131 / rank | |||
Property / reviewed by | |||
Property / reviewed by: William G. Brown / rank | |||
Property / author | |||
Property / author: Pavol Hell / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: William G. Brown / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00373-007-0712-5 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1964336276 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Star-cutsets and perfect graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Recognizing Berge graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The strong perfect graph theorem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4521527 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: List Partitions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3328583 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Either tournaments or algebras? / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Duality theorems for finite structures (characterising gaps and good characterisations) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3208855 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 12:28, 26 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the density of trigraph homomorphisms |
scientific article |
Statements
On the density of trigraph homomorphisms (English)
0 references
19 July 2007
0 references
A trigraph \(G\) consists of a finite set \(V(G)\) of vertices, and two (possibly intersecting) edge sets \(E_1(G)\), \(E_2(G)\) on \(V(G)\), such that \(E_1(G)\cup E_2(G)\) contains all unordered pairs of (possibly equal) vertices. Let \(G\) and \(H\) be any trigraphs. A homomorphism \(f\) of \(G\) to \(H\) is a mapping of \(V(G)\) to \(V(H)\) such that \(uv\in E_i(G)\) implies \(f(u)f(v)\in E_i(H)\) (\(i=1,2\)). \(G<H\) means that there exists a homomorphism of \(G\) to \(H\), but not of \(H\) to \(G\); if \(G<H\) but there exists no \(K\) such that \(G<K<H\), \(G<H\) is called a gap. From the authors' abstract: ``An order is dense if \(A<B\) implies \(A<C<B\) for some \(C\). The homomorphism order of (nontrivial) graphs is known to be dense. Homomorphisms of trigraphs extend homomorphisms of graphs'' [cf. \textit{P. Hell} and \textit{J. Nešetřil}, Graphs and homomorphisms. Oxford University Press (2004; Zbl 1062.05139)], ``and model many partitions of interest in the study of perfect graphs.'' Two trigraphs are homomorphically equivalent if each admits a homomorphism to the other. A trigraph is a core if it is not homomorphically equivalent to any proper subtrigraph. A digon (respectively diloop) of \(G\) is a pair \(u,v\) of distinct (respectively identical) vertices such that \(uv\in E_1(G)\cap E_2(G)\); \(G^*\) is the subtrigraph induced by all vertices incident to digons. Theorem 1. Suppose \(G\) and \(H\) are cores without diloops such that \(G<H\). If (1) \(G\) is a subtrigraph of \(H\) with \(G^*=H^*\); (2) every homomorphism of \(G\) to \(H\) is injective; and (3) the core of each proper subtrigraph of \(H\) which contains \(G\) is equal to \(G\), then \(G<H\) is a gap. Otherwise there exists a trigraph \(K\) with \(G<K<H\).
0 references
trigraph
0 references
homomorphism
0 references
density
0 references
gap
0 references
perfect graph
0 references
0 references