Vertex coverings by coloured induced graphs — Frames and Umbrellas (Q3024632)

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 2185450
Language Label Description Also known as
default for all languages
No label defined
    English
    Vertex coverings by coloured induced graphs — Frames and Umbrellas
    scientific article; zbMATH DE number 2185450

      Statements

      Vertex coverings by coloured induced graphs — Frames and Umbrellas (English)
      0 references
      0 references
      0 references
      1 July 2005
      0 references
      homogeneously embeds
      0 references
      uniformly embeds
      0 references
      \(k\)-edge-coloring
      0 references
      bicliques
      0 references
      cliques
      0 references
      stars
      0 references
      For a graph \(G\) and integer \(k>0\) denote by \(f_k(G)\) the minimum order of a graph \(H\) whose edges can be \(k\)-colored so that \(G\) homogeneously embeds in the induced graph by edges of each color. That is, for all vertices \(x,y\) of \(G\) and \(H\), respectively, there is an induced copy of \(G\) in \(H\) with \(x\) at \(y\). In a similar setup, denote by \(g_k(G)\) the minimum order of \(H\) such that \(G\) uniformly embeds in \(H\). That is, for every vertex \(y\) of \(H\) there is an induced copy of \(G\) containing \(y\). The paper contains some properties of the numbers \(f_k\) and \(g_k\) and results for special graph classes. In particular, exact results for \(f_2\) are presented for \(K_{1,b}\), \(K_{a,b}\) with \(2\leq q\leq b/2\), \(f_2(K_{b,b})=3b/2\) for \(b\) even, and \(f_2(K_{b,b})\geq 3b\) in general. The main result concerning \(g_2\) is the lower bound \(g_2(K_{a,b})\geq \min(2b,b+3a)\) with equality if \(b\geq 2a\). Some particular results are also presented for cliques for \(k=3\).
      0 references

      Identifiers