The chromatic discrepancy of graphs
For a proper vertex coloring c c of a graph G G , let ?c(G) ? c ( G ) denote the maximum, over all induced subgraphs H H of G G , the difference between the chromatic number ?(H) ? ( H ) and the number of colors used by c c to color H H . We define the chromatic discrepancy of a graph G G , denoted by ?(G) ? ( G ) , to be the minimum ?c(G) ? c ( G ) , over all proper colorings c c of G G . If H H is restricted to only connected induced subgraphs, we denote the corresponding parameter by ?  ( G ) . These parameters are aimed at studying graph colorings that use as few colors as possible in a graph and all its induced subgraphs. We study the parameters ?(G) ? ( G ) and ?  ( G ) and obtain bounds on them. We obtain general bounds, as well as bounds for certain special classes of graphs including random graphs. We provide structural characterizations of graphs with ?(G)=0 ? ( G ) = 0 and graphs with ?  ( G ) = 0 . We also show that computing these parameters is NP-hard.
chromatic discrepancy graph coloring random graphs graph theory local coloring