Grzesik, Andrzej and Győri, Ervin and Salia, Nika and Tompkins, Casey (2023) Subgraph densities in Kr-free graphs. ELECTRONIC JOURNAL OF COMBINATORICS, 30 (1). ISSN 1097-1440
|
Text
2205.13455v1.pdf Download (106kB) | Preview |
Abstract
A counterexample to a recent conjecture of LidickATIN SMALL LETTER Y WITH ACUTE and Murphy on the structure of Kr-free graph maximizing the number of copies of a given graph with chromatic number at most r -1 is known in the case r = 3. Here, we show that this conjecture does not hold for any r, and that the structure of extremal graphs can be richer. We also provide an alternative conjecture and, as a step towards its proof, we prove an asymptotically tight bound on the number of copies of any bipartite graph of radius at most 2 in the class of triangle-free graphs.Mathematics Subject Classifications: 05C35
| Item Type: | Article |
|---|---|
| Additional Information: | Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary Extremal Combinatorics and Probability Group, Institute for Basic Science, Daejeon, South Korea Cited By :1 Export Date: 20 February 2024 Funding details: Narodowe Centrum Nauki, NCN, 2021/42/E/ST1/00193 Funding details: Institute for Basic Science, IBS, IBS-R029-C4, K135800 Funding details: National Research, Development and Innovation Office, K132696, SNN-135643 Funding text 1: ∗Supported by the National Science Centre grant 2021/42/E/ST1/00193. †Supported by the National Research, Development and Innovation Office NKFIH grants K132696 and SNN-135643. ‡Supported by the National Research, Development and Innovation Office NKFIH grants K132696 and SNN-135643, and by the Institute for Basic Science (IBS-R029-C4). §Supported by the National Research, Development and Innovation Office NKFIH grant K135800. |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 30 Mar 2024 11:47 |
| Last Modified: | 30 Mar 2024 11:47 |
| URI: | https://real.mtak.hu/id/eprint/191304 |
Actions (login required)
 |
Edit Item |
