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
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
0.8871031
0 references
0 references
0.8725117
0 references
0 references
0 references
0 references
0.8666998
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