Counterexamples to Two Conjectures on Mean Color Numbers of Graphs
Abstract
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.
Fields of Study & Subjects
Graph Labeling and Dimension Problems
Limits and Structures in Graph Theory
Graph theory and applications
Publication details
- Journal / source
- Journal of Graph Theory
- Volume
- 113
- Issue
- 1
- Pages
- 57–60
- Publication date
- 23 April 2026
- Language
- EN