Counterexamples to Two Conjectures on Mean Color Numbers of Graphs
Wushuang Zhai, Yan Yang · Journal of Graph Theory · 2026
ABSTRACT The mean color number of an ‐vertex graph , denoted by , is the average number of colors used in all proper ‐colorings of . For any graph and any vertex in , Dong (2003) conjectured that (1) ; (2) if is not an isolated vertex, then , where is a graph obtained from by deleting all but one of the edges incident to . We disprove these two conjectures by providing an infinite family of counterexamples.