Name
Abstract | ||
|---|---|---|
Alon, Balogh, Keevash, and Sudakov proved that the (k-1)-partite Turan graph maximizes the number of distinct r-edge-colorings with no monochromatic K-k for all fixed k and r = 2, 3, among all n-vertex graphs. In this paper, we determine this function asymptotically for r = 2 among n-vertex graphs with a sublinear independence number. Somewhat surprisingly, unlike Alon, Balog, Keevash, and Sudakov's result, the extremal construction from Ramsey-Turan theory, as a natural candidate, does not maximize the number of distinct edge-colorings with no monochromatic cliques among all graphs with a sublinear independence number, even in the 2-colored case. In the second problem, we determine the maximum number of triangles asymptotically in an n-vertex K-k free graph G with alpha(G) = o(n). The extremal graphs have a similar structure to the extremal graphs for the classical Ramsey-Turan problem, i.e., when the number of edges is maximized. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1137/16M1086078 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
Ramsey-Turan,edge-coloring,monochromatic cliques | Discrete mathematics,Graph,Independence number,Combinatorics,Monochromatic color,Chordal graph,Mathematics | Journal |
Volume | Issue | ISSN |
31 | 3 | 0895-4801 |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| József Balogh | 1 | 862 | 89.91 |
| Hong Liu | 2 | 39 | 8.54 |
| Maryam Sharifzadeh | 3 | 11 | 3.83 |