پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 42 |
| تعداد شماره‌ها | 1,537 |
| تعداد مقالات | 12,623 |
| تعداد مشاهده مقاله | 25,826,486 |
| تعداد دریافت فایل اصل مقاله | 10,661,408 |
Counterexamples to a conjecture on matching Kneser graphs | ||
| Transactions on Combinatorics | ||
| دوره 12، شماره 3، آذر 2023، صفحه 172-173 اصل مقاله (357.83 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22108/toc.2022.132638.1961 | ||
| نویسنده | ||
| Moharram N. Iradmusa* | ||
| Department of Mathematical Sciences, Shahid Beheshti University. | ||
| چکیده | ||
| Let $G$ be a graph and $r\in\mathbb{N}$. The matching Kneser graph $\textsf{KG}(G, rK_2)$ is a graph whose vertex set is the set of $r$-matchings in $G$ and two vertices are adjacent if their corresponding matchings are edge-disjoint. In [M. Alishahi and H. Hajiabolhassan, On the Chromatic Number of Matching Kneser Graphs, Combin. Probab. and Comput., 29, No. 1 (2020), 1--21] it was conjectured that for any connected graph $G$ and positive integer $r\geq 2$, the chromatic number of $\textsf{KG}(G, rK_2)$ is equal to $|E(G)|-\textsf{ex}(G,rK_2)$, where $\textsf{ex}(G,rK_2)$ denotes the largest number of edges in $G$ avoiding a matching of size $r$. In this note, we show that the conjecture is not true for snarks. | ||
| کلیدواژه‌ها | ||
| matching Kneser graph؛ snarks؛ chromatic number | ||
| مراجع | ||
|
[1] M. Alishahi and H. Hajiabolhassan, On the Chromatic Number of Matching Kneser Graphs, Combin. Probab. and Comput., 29 (2020) 1–21. [2] M. Gardner, Mathematical Games, Scientific American, 234 (1976) 126–130.
[3] L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A, 25 (1978) 319–324.
[4] J. Petersen, Die Theorie der regulären graphs, Acta Mathematica, 15 (1891) 193–220.
[5] T. Schönberger, Ein Beweis des Petersenschen Graphensatzes, Acta Sci. Math. (Szeged), 7 (1934-5) 51–57. | ||
|
آمار تعداد مشاهده مقاله: 195 تعداد دریافت فایل اصل مقاله: 182 |
||