The chromatic discrepancy of graphs

N R, Aravind and Kalyanasundaram, S and R B, Sandeep and Sivadasan, N (2015) The chromatic discrepancy of graphs. Discrete Applied Mathematics, 184. pp. 40-49. ISSN 0166-218X

Text (Author version preprint)
1401.3251.pdf - Accepted Version

Download (388kB) | Preview


For a proper vertex coloring cc of a graph GG, let φc(G)φc(G) denote the maximum, over all induced subgraphs HH of GG, the difference between the chromatic number χ(H)χ(H) and the number of colors used by cc to color HH. We define the chromatic discrepancy of a graph GG, denoted by φ(G)φ(G), to be the minimum φc(G)φc(G), over all proper colorings cc of GG. If HH is restricted to only connected induced subgraphs, we denote the corresponding parameter by View the MathML sourceφˆ(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 View the MathML sourceφˆ(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 View the MathML sourceφˆ(G)=0. We also show that computing these parameters is NP-hard.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Article
Additional Information: We gratefully acknowledge Manu Basavaraju, L. Sunil Chandran, Mathew C. Francis and Bheemarjuna Reddy Tamma for fruitful discussions. The third author was supported by TCS Research Scholarship.
Uncontrolled Keywords: Graph theory; Graph coloring; Chromatic discrepancy; Random graphs; Local coloring
Subjects: Computer science > Big Data Analytics
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 23 Jun 2015 05:25
Last Modified: 08 Jan 2016 06:38
Publisher URL:
OA policy:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 1593 Statistics for this ePrint Item