Hypergraph incidence coloring

Abstract

An incidence of a hypergraph $\mathcal{H}=(X,S)$ is a pair $(x,s)$ with $x\in X$, $s\in S$ and $x\in s$. Two incidences $(x,s)$ and $(x^{\prime },s^{\prime })$ are adjacent if (i) $x=x^{\prime }$, or (ii) $\{x,x^{\prime }\}\subseteq s$ or $\{x,x^{\prime }\}\subseteq s^{\prime }$. A proper incidence $k$-coloring of a hypergraph $\mathcal{H}$ is a mapping $\phi$ from the set of incidences of $\mathcal{H}$ to $\{1,2,\dots ,k\}$ so that $\phi (x,s)\ne \phi (x^{\prime },s^{\prime })$ for any two adjacent incidences $(x,s)$ and $(x^{\prime },s^{\prime })$ of $\mathcal{H}$. The incidence chromatic number ${\chi }_I(\mathcal{H})$ of $\mathcal{H}$ is the minimum integer $k$ such that $\mathcal{H}$ has a proper incidence $k$-coloring. In this paper we prove ${\chi }_I(\mathcal{H})\le (4/3+o(1))r(\mathcal{H})\Delta (\mathcal{H})$ for every $t$-quasi-linear hypergraph with $t<<r(\mathcal{H})$ and sufficiently large $\Delta (\mathcal{H})$, where $r(\mathcal{H})$ is the maximum of the cardinalities of the edges in $\mathcal{H}$. It is also proved that ${\chi }_I(\mathcal{H})\le \Delta (\mathcal{H})+r(\mathcal{H})-1$ if $\mathcal{H}$ is an $\alpha$-acyclic linear hypergraph, and this bound is sharp.

17 pages