Some properties and applications of odd-colorable $r$-hypergraphs

Abstract

Let $r\ge 2$ and $r$ be even. An $r$-hypergraph $G$ on $n$ vertices is called odd-colorable if there exists a map $\phi :[n]\to [r]$ such that for any edge $\{j_1,j_2,\cdots ,j_r\}$ of $G$, we have $\phi (j_1)+\phi (j_2)+\cdot \cdot \cdot +\phi (j_r)\equiv r/2(\mathrm{mod}r).$ In this paper, we first determine that, if $r=2^q(2t+1)$ and $n\ge 2^q(2^q-1)r$, then the maximum chromatic number in the class of the odd-colorable $r$-hypergraphs on $n$ vertices is $2^q$, which answers a question raised by V. Nikiforov recently in [V. Nikiforov, Hypergraphs and hypermatrices with symmetric spectrum. Prinprint available in arXiv:1605.00709v2, 10 May, 2016]. We also study some applications of the symmetric spectral property of the odd-colorable $r$-graphs given in that same paper by V. Nikiforov. We show that the Laplacian spectrum and the signless Laplacian spectrum of an $r$-hypergraph $G$ are equal if and only if $G$ is odd-colorable, and then study some further applications of these spectral properties.

9pages; Some results are added, and some typos are corrected

References in corpus (2)

• The Eigenvectors of the Zero Laplacian and Signless Laplacian Eigenvalues of a Uniform Hypergraph
• Hypergraphs and hypermatrices with symmetric spectrum

Cited by in corpus (1)

• Sharp lower bounds on the spectral radius of uniform hypergraphs concerning degrees