MathCastle
Graph TheoryMediumGraph Coloring

Graph Coloring · Medium problem

A central router cc connects directly to three devices x,y,zx,y,z, and device xx also connects to one more device ww (a small tree network, 44 links in all). Coloring in the order w,y,z,x,cw,y,z,x,c — each device getting the smallest color not already used by an earlier-colored neighbor — uses some number of colors. By how many more colors does this order use compared to the TRUE chromatic number of the network?