2022/02/06 by Weichan Liu, Guiying Yan, Liu, Weichan +1
Engineering · Neuroscience · #graph theory and CDMA systems #Nuclear Receptors and Signaling
paper · pdf · doi:10.48550/arxiv.2202.02770
An incidence of a hypergraph H=(X,S) is a pair (x,s) with x∈ X, s∈ S and x∈ s. Two incidences (x,s) and (x',s') are adjacent if (i) x=x', or (ii) \x,x'\⊆ s or \x,x'\⊆ s'. A proper incidence k-coloring of a hypergraph H is a mapping φ from the set of incidences of H to \1,2,…,k\ so that φ(x,s)≠ φ(x',s') for any two adjacent incidences (x,s) and (x',s') of H. The incidence chromatic number χI(H) of H is the minimum integer k such that H has a proper incidence k-coloring. In this paper we prove χI(H)≤ (4/3+o(1))r(H)Δ(H) for every t-quasi-linear hypergraph with t<