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

Preview

Text (Author version preprint)
1401.3251.pdf - Accepted Version
Download (388kB) | Preview

Abstract

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 Creators	ORCiD
N R, Aravind	UNSPECIFIED
Sivadasan, N	UNSPECIFIED

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