
doi: 10.1007/bf01300130
To each graph \(H\) on \(n\) vertices we may associate a 2-coloring of the edges of the complete graph \(K_n\) by taking the edges of \(H\) to be one color class and the edges of its complement \(\overline H\) to be the other. Given a coloring \(H\), we define \(c(G; H)\) to be the proportion of the copies of \(G\) in \(K_n\) which are monochromatic and \(c(G; n)\) to be the minimum of \(c(G; H)\) over all colorings \(H\) of \(K_n\). It is not difficult to show that \(c(G; n)\) has a limit as \(n\to \infty\), which we denote by \(c(G)\). The average value of \(c(G; H)\) over all graphs \(H\) is \(2^{1- e(G)}\); hence, \(c(G)\leq 2^{1- e(G)}\). A graph \(G\) is said to be common if the equality holds and uncommon if the strict inequality holds. The authors prove several interesting results about these concepts including Theorem 8: The even wheel \(W_{2k}\) is common for \(k\geq 2\). And their main result is Theorem 12: Every graph containing \(K_4\) is uncommon.
Extremal problems in graph theory, common graph, Generalized Ramsey theory, wheel, coloring
Extremal problems in graph theory, common graph, Generalized Ramsey theory, wheel, coloring
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 37 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
