Hypergraph incidence coloring

DOI10.1016/J.DISC.2022.113311MaRDI QIDQ6390276arXivFDO

Authors Weichan Liu, Guiying Yan

Publication date 6 February 2022

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.DISC.2022.113311

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

arXiv classification

math.CO

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

This page was built for publication: Hypergraph incidence coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6390276)