Some properties and applications of odd-colorable r-hypergraphs

Xiying Yuan, Liqun Qi, Jiayu Shao, Chen Ouyang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

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 languageEnglish
Pages (from-to)446-452
Number of pages7
JournalDiscrete Applied Mathematics
Volume236
DOIs
Publication statusPublished - 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

Cite this