التفاصيل البيبلوغرافية
| العنوان: |
A STABILITY RESULT FOR C2k+1-FREE GRAPHS. |
| المؤلفون: |
SIJIE REN, JIAN WANG, SHIPENG WANG, WEIHUA YANG |
| المصدر: |
SIAM Journal on Discrete Mathematics; 2024, Vol. 38 Issue 2, p1733-1756, 24p |
| مصطلحات موضوعية: |
BIPARTITE graphs |
| مستخلص: |
A graph G is called C2k+1-free if it does not contain any cycle of length 2k + 1. In 1962, Erdös (together with Gallai), and independently Andrásfai, proved that every n-vertex triangle-free graph with more than (n-1)²/4 + 1 edges is bipartite. In this paper, we extend their result and show that for 1 ≤ t 2k - 2 and 2 ≥ 318²k, every n-vertex C2k+1-free graph with more than (n-t-1)²/4 + (t+2) edges can be made bipartite by either deleting at most t - 1 vertices or deleting at most (⌊t-2⌋/2) + (⌈t+2⌉/2) - 1 edges. The construction shows that this is best possible. [ABSTRACT FROM AUTHOR] |
|
Copyright of SIAM Journal on Discrete Mathematics is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Complementary Index |
