Coloring 2-intersecting hypergraphs

MaRDI QIDQ396868zbMATH OpenFDO

Authors Lucas Colucci, András Gyárfás

Publication date 14 August 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.6944, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i3p37

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

hypergraph coloring

Mathematics Subject Classification ID

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

Abstract: A hypergraph is 2-intersecting if any two edges intersect in at least two vertices. Blais, Weinstein and Yoshida asked (as a first step to a more general problem) whether every 2-intersecting hypergraph has a vertex coloring with a constant number of colors so that each hyperedge e has at least min{|e|,3} colors. We show that there is such a coloring with at most 5 colors (which is best possible).

Recommendations

• On the \(c\)-strong chromatic number of \(t\)-intersecting hypergraphs
• Semi-strong colouring of intersecting hypergraphs
• On the degree, size, and chromatic index of a uniform hypergraph
• Coloring hypergraphs with bounded cardinalities of edge intersections
• Exact algorithms for list-coloring of intersecting hypergraphs

Cites work

• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• On the \(c\)-strong chromatic number of \(t\)-intersecting hypergraphs

Cited in

(4)

• On the \(c\)-strong chromatic number of \(t\)-intersecting hypergraphs
• Exact algorithms for list-coloring of intersecting hypergraphs
• Semi-strong colouring of intersecting hypergraphs
• The intersection spectrum of 3‐chromatic intersecting hypergraphs

This page was built for publication: Coloring 2-intersecting hypergraphs

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