scientific article; zbMATH DE number 4031753
[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.
- Homomorphisms of complete n-partite graphs
- Inequalities with respect to graph homomorphism
- Fractional multiples of graphs and the density of vertex-transitive graphs
- Homomorphisms of binary Cayley graphs
- Symmetric linear spaces of graphs
- scientific article; zbMATH DE number 3853146 (Why is no real title available?)
- scientific article; zbMATH DE number 2151249 (Why is no real title available?)
- scientific article; zbMATH DE number 6303010 (Why is no real title available?)
- On symmetric equivalence of symmetric union diagrams
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3772263)