×

zbMATH — the first resource for mathematics

On the chromatic number of a simplicial complex. (English) Zbl 1399.05227
The chromatic number \(\chi(G)\) of a graph \(G\) is the minimal number of colors needed to color its vertices \(V\) in such a way that no edge is monochromatic. It has been studied extensively by different methods. The spectral method bounds \(\chi(G)\) by means of the spectra of various operators is defined on the graph. An advantage of the method is that the spectrum of an operator on a finite graph can be calculated in polynomial time, while the problem of finding the chromatic number of a graph is NP-complete. The Laplacian \(\Delta\) of a graph \(G\) is an operator on the space \(C^0\) of the real-valued functions on the vertex set \(V\) of \(G\) acting by the rule \[ \Delta f(v)=\operatorname{deg}v\cdot f(v)-\sum_{u\sim v}f(u), \] where \(\text{deg}v\), \(v\in V\), is the number of vertices adjacent to \(v\), and \(u\sim v\) means that \(u\) and \(v\) are connected by an edge. The paper A. J. Hoffman [in: Graph theory and its applications. Proceedings of an advanced seminar conducted by the Mathematics Research Center, United States Army, at the University of Wisconsin, Madison, October 13–15, 1969. New York - London: Academic Press. 79–91 (1970; Zbl 0221.05061)] gives a lower bound on the chromatic number of a graph in the terms of the largest and the smallest eigenvalues of its adjacency matrix.
In the paper under review, the author establishes a higher dimensional version of this result and gives a lower bound on the chromatic number of a pure \(d\)-dimensional simplicial complex in terms of the spectra of the higher Laplacian operators introduced in B. Eckmann, [Comment. Math. Helv. 17, 240–255 (1945; Zbl 0061.41106)].
The finite pure \(d\)-dimensional abstract simplicial complex is a family \(X\) of subsets (called faces) of a finite vertex set \(V\) closed under taking subsets, such that every maximal subset in the family is of size \(d+1\). The chromatic number \(\chi(X)\) is the least number of colors needed to color its vertices in such a way that no maximal face is monochromatic. In the special case of a pure \(d\)-dimensional simplicial complex with a complete \((d-1)\)-skeleton, a different shorter proof is given.

MSC:
05E45 Combinatorial aspects of simplicial complexes
05A20 Combinatorial inequalities
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] M. Deza and P. Frankl: On the maximum number of permutations with given maximal or minimal distance, Journal of Combin · Zbl 0352.05003
[2] B. Eckmann: Harmonische Funktionen und Randwertaufgaben in einem Komplex, Commentar · Zbl 0061.41106
[3] A. J. Hoffman: On Eigenvalues and Colorings of Graphs, Graph Theory and its Applications, (ed: B. Harris), Academic Press, (1970), 79–91.
[4] D. Horak and J. Jost: Spectra of combinatorial Laplace operators on simplicial complexes, · Zbl 1290.05103
[5] L. Lovász: On the Shannon capacity of a graph, IEEE Transactions of Information Theory, IT-25(1), (1979), 1–7. · Zbl 0395.94021
[6] A. Lubotzky, R. Phillips and P. Sarnak: Ramanuj · Zbl 0661.05035
[7] O. Parzanchevski, R. Rosenthal, R. J. Tessler: Isoperimetric Inequalities in Simplicial · Zbl 1389.05174
[8] P. Renteln: On the Spectrum of the Derangement Graph, Electronic · Zbl 1183.05047
[9] H. S. Wilf: The Eigenvalues of a Graph and Its Chromatic Number, Journal of the Lon · Zbl 0144.45202
[10] P. Wocjan and C. Elphick: New Spectral Bounds on the Chromatic Number Encompassing all Eigenvalues of the Adjacency Matrix. Electronic · Zbl 1295.05112
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.