Abstract
Let r≥2 and r be even. An r-hypergraph G on n vertices is called odd-colorable if there exists a map φ:[n]→[r] such that for any edge {j1,j2,…,jr} of G, we have φ(j1)+φ(j2)+⋅⋯⋅+φ(jr)≡r∕2(modr). In this paper, we first determine that, if r=2q(2t+1) and n≥2q(2q−1)r, then the maximum chromatic number in the class of the odd-colorable r-hypergraphs on n vertices is 2q, which answers a question raised by V. Nikiforov recently in Nikiforov (2017). We also study some applications of the spectral symmetry of the odd-colorable r-hypergraphs given in the same paper by V. Nikiforov. We show that the Laplacian spectrum Spec(L(G)) and the signless Laplacian spectrum Spec(Q(G)) of an r-hypergraph G are equal if and only if r is even and G is odd-colorable. As an application of this result, we give an affirmative answer for the remaining unsolved case r⁄≡0(mod4) of a question raised in Shao et al. (2015) about whether Spec(L(G))=Spec(Q(G)) implies that L(G) and Q(G) have the same H-spectrum.
Original language | English |
---|---|
Pages (from-to) | 446-452 |
Number of pages | 7 |
Journal | Discrete Applied Mathematics |
Volume | 236 |
DOIs | |
Publication status | Published - 19 Feb 2018 |
Keywords
- Chromatic number
- Laplacian spectrum
- Odd-colorable
- r-hypergraph
- Signless Laplacian spectrum
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics