pith. sign in

arxiv: 2405.01890 · v2 · pith:6N2F7GOQnew · submitted 2024-05-03 · 🧮 math.CO

Counterexamples to two conjectures on mean color numbers of graphs

classification 🧮 math.CO
keywords graphcolorconjecturedconjecturescounterexamplesmeannumbervertex
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.