Counterexamples to two conjectures on mean color numbers of graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929380757864448 |
|---|---|
| author | Zhai, Wushuang Yang, Yan |
| author_facet | Zhai, Wushuang Yang, Yan |
| contents | The mean color number of an $n$-vertex graph $G$, denoted by $μ(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 $μ(G)\geq μ(H)$; and also conjectured that $μ(G)\geq μ((G-w)\cup K_1)$. We prove that there is an infinite family of counterexamples to these two conjectures. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_01890 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Counterexamples to two conjectures on mean color numbers of graphs Zhai, Wushuang Yang, Yan Combinatorics 05C15, 05C30, 05C31 The mean color number of an $n$-vertex graph $G$, denoted by $μ(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 $μ(G)\geq μ(H)$; and also conjectured that $μ(G)\geq μ((G-w)\cup K_1)$. We prove that there is an infinite family of counterexamples to these two conjectures. |
| title | Counterexamples to two conjectures on mean color numbers of graphs |
| topic | Combinatorics 05C15, 05C30, 05C31 |
| url | https://arxiv.org/abs/2405.01890 |