scientific article; zbMATH DE number 19174

[For the entire collection see Zbl 0734.00014.] Let \({\mathcal G}= ({\mathcal G}_1,\dots ,{\mathcal G}_k)\) be a \(k\)-tuple of non-empty sets of graphs. For a graph \(F\), the relation \(F\to {\mathcal G}\) indicates that, whenever the edges of \(F\) are colored with \(k\) colors, there is an index \(i\) and graph \(G\in {\mathcal G}_i\) so that there is a subgraph of \(F\) isomorphic to \(G\) with all edges assigned color \(i\). Now let \({\mathcal F}\) be a family of graphs and define \(ex(n;{\mathcal F})\) to be the maximum number of edges that a graph on \(n\) vertices can have without containing a subgraph isomorphic to a graph in \({\mathcal F}\). If \({\mathcal F}\) is the set of graphs \(F\) so that \(F\not\to {\mathcal G}\) we replace \(ex(n,{\mathcal F})\) with \(ex(n;\not\to {\mathcal G})\). Starting with the simple upper bound: \[ ex(n;\not\to {\mathcal G})\leq\sum_{1\leq i\leq h}ex(n;{\mathcal G}_i) \] the authors prove a variety of interesting equalities and inequalities about \(ex(n;\not\to {\mathcal G})\).

Recommendations

Cited in

(7)

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 Q3976602)