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

      0 references
      0 references
      1986
      0 references
      symmetric graph
      0 references
      homomorphism
      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

      Identifiers