تقرير
Counterexamples to two conjectures on mean color numbers of graphs
| العنوان: | Counterexamples to two conjectures on mean color numbers of graphs |
|---|---|
| المؤلفون: | Zhai, Wushuang, Yang, Yan |
| سنة النشر: | 2024 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, 05C15, 05C30, 05C31 |
| الوصف: | The mean color number of an $n$-vertex graph $G$, denoted by $\mu(G)$, is the average number of colors used in all proper $n$-colorings of $G$. For any graph $G$ and a vertex $w$ in $G$, Dong (2003) conjectured that if $H$ is a graph obtained from a graph $G$ by deleting all but one of the edges which are incident to $w$, then $\mu(G)\geq \mu(H)$; and also conjectured that $\mu(G)\geq \mu((G-w)\cup K_1)$. We prove that there is an infinite family of counterexamples to these two conjectures. Comment: 6 pages |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2405.01890 |
| رقم الأكسشن: | edsarx.2405.01890 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |