Zhouyun Jiang

An Edwards-type lower bound for the maximum k-cut of a connected graph

Let G be a finite simple connected graph with n vertices and m edges, and let f_k(G) denote the maximum number of bichromatic edges over all k-colorings of G. We prove that for every integer k ≥ 3, f_k(G) ≥ (k−1)m/k + (n−1)/k. Equivalently, the minimum number es_k(G) of edges who...