No label defined (Q3772263)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4031753
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4031753 |
Statements
1986
0 references
symmetric graph
0 references
homomorphism
0 references
0.7855534553527832
0 references
0.7677179574966431
0 references
[For the entire collection see Zbl 0608.00004.] Given two graphs G, H set \(G<H\) if there is a homomorphism \((=\) edge preserving map) from G into H but none from H to G. Let \(I(G,H)=\{K\); \(G<K<H\}\). \textit{E. Welzl} [Theor. Comput. Sci. 17, 29-41 (1982; Zbl 0482.68063)] showed that if \(G<H\), H not bipartite, then there exists a \(K\in I(G,H)\); moreover he conjectured that if both G and H are symmetric then K can be chosen to be symmetric as well. The authors prove this conjecture for the case when G is a cycle with \(2j+1\) vertices and the independence ratio of H is less than \(j/(2j+1)\). They also prove that for each symmetric non-bipartite graph G there is a H such that \(G<H\) and no member in I(G,H) is symmetric.
0 references