An inertial lower bound for the chromatic number of a graph. (English) Zbl 1358.05104

Elphick, Clive; Wocjan, Pawel

Electron. J. Comb. 24, No. 1, Research Paper P1.58, 9 p. (2017).

Summary: Let \(\chi(G\)) and \(\chi_f(G)\) denote the chromatic and fractional chromatic numbers of a graph \(G\), and let \((n^+, n^0, n^-)\) denote the inertia of \(G\). We prove that: \[ 1 + \max\bigg(\frac{n^+}{n^-},\frac{n^-}{n^+}\bigg) \leq \chi(G) \] and conjecture that \[ 1 + \max\bigg(\frac{n^+}{n^-},\frac{n^-}{n^+}\bigg) \leq \chi_f(G). \] We investigate extremal graphs for these bounds and demonstrate that this inertial bound is not a lower bound for the vector chromatic number. We conclude with a discussion of asymmetry between \(n^+\) and \(n^-\), including some Nordhaus-Gaddum bounds for inertia.

MSC:

05C15	Coloring of graphs and hypergraphs
05C50	Graphs and linear algebra (matrices, eigenvalues, etc.)

Keywords:

spectral graph theory; chromatic number; fractional chromatic number

References:

[1]	T. Ando and M. Lin, Proof of a conjectured lower bound on the chromatic number of a graph, Lin. Algebra and Appl., 485, (2015), 480 - 484. the electronic journal of combinatorics 24(1) (2017), #P1.588 · Zbl 1322.05054
[2]	M. Aouchiche and P. Hansen, A survey of Nordhaus-Gaddum type relations, Discrete Appl. Math. 161, (2017), 466-546. · Zbl 1259.05083
[3]	Y. Bilu, Tales of Hoffman: Three extensions of Hoffman’s bound on the graph chromatic number, J. Combin. Theory Ser. B, 96 (2006), 608 - 613. · Zbl 1094.05036
[4]	A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Universitext, (2010). · Zbl 1231.05001
[5]	J. I. Brown and R. Hoshino, Nordhaus-Gaddum inequalities for the fractional and circular chromatic numbers, Discrete Math., 309, (2009), 2223 - 2232. · Zbl 1198.05039
[6]	D. Cvetkovi´c, M. Doob and H. Sachs, Spectra of Graphs, Academic Press, New York, (1979).
[7]	C. Elphick and P.Wocjan, Unified spectral bounds for the chromatic number, Discussiones Mathematicae Graph Theory, 35, (2015), 773 - 780. · Zbl 1326.05080
[8]	C. Godsil and K. Meagher, Erdos-Ko-Rado Theorems: Algebraic Approaches, Cambridge University Press, (2015). · Zbl 1343.05002
[9]	D. A. Griffith and U. Luhanga, Approximating the inertia of the adjacency matrix of a connected planar graph that is the dual of a geographic surface partitioning, Geographical Analysis 43, (2011), 383 - 402.
[10]	A. J. Hoffman, On eigenvalues and colorings of graphs, in: Graph Theory and its Applications (B. Harris, ed.), Acad. Press, New York, (1970). · Zbl 0221.05061
[11]	L. Yu Kolotilina, Inequalities for the extreme eigenvalues of block-partitioned Hermitian matrices with applications to spectral graph theory, J. Math Sci. 176 (2011), 44 - 56 (translation of the paper originally published in Russian in Zapiski Nauchnykh Seminarov POMI 382 (2010), 82 - 103). · Zbl 1291.15050
[12]	L. S. de Lima, C. S. Oliveira, N. M. M. de Abreu and V. Nikiforov, The smallest eigenvalue of the signless Laplacian, Linear Algebra Appl., 435, (2011), 2570 2584. · Zbl 1222.05180
[13]	V. Nikiforov, Chromatic number and spectral radius, Linear Algebra Appl., 426, (2007), 810 - 814. · Zbl 1125.05063
[14]	V. Nikiforov, Extrema of graph eigenvalues, Linear Algebra Appl., 482, (2015), 158 - 190. · Zbl 1330.05105
[15]	E.A. Nordhaus and J. W. Gaddum, On Complementary Graphs, Amer. Math. Monthly, 63 (1956), 175 - 177. · Zbl 0070.18503
[16]	P. Wocjan and C. Elphick, New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix, Electronic J. Combin., 20(3), (2013), #P39. the electronic journal of combinatorics 24(1) (2017), #P1.589 · Zbl 1295.05112