Mean Color Numbers of Some Graphs

作者：Long, Shude^*; Ren, Han

来源：GRAPHS AND COMBINATORICS, 2022, 38(1): 14.

DOI：10.1007/s00373-021-02412-8

• Graph
• Chromatic polynomial
• Mean color number
• Simplicial vertex
• Wheel

Let mu(G) denote the mean color number of a graph G. Dong proposed two mean color conjectures. One is that for any graph G and a vertex w in G with d(w) > 1, if H is a graph obtained from G by deleting all but one of the edges which are incident to w, then it(G)> it(H). The other is that for any graph G and a vertex w in G, it(G)>.((G w) U In this paper, we show that the two conjectures hold under the condition that w is a simplicial vertex in G. And when G is a connected (n, m) graph and w is not a cut vertex in G with d(w) = n 1, if rn < + 2) n 4.5 the second conjecture holds too. The two conjectures also hold for some special cases, such as wheels and chordal graphs (Dong in J Combin Theory Ser B 87: 348-365, 2003).