Graph Theorymedium
0:00.0

Let GG be a connected graph with chromatic number χ(G)=4\chi(G) = 4. If we identify a bridge (cut-edge) in GG and remove it, what is the minimum possible chromatic number of the resulting graph?