Semi-strong colouring of intersecting hypergraphs

DOI10.1017/S0963548313000515MaRDI QIDQ5414142zbMATH OpenFDO

Authors Eric Blais, Amit Weinstein, Yuichi Yoshida

Publication date 2 May 2014

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.2868

zbMATH Keywords

chromatic numberintersecting hypergraphssemi-strong colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: For any c >= 2, a c-strong coloring of the hypergraph G is an assignment of colors to the vertices of G such that for every edge e of G, the vertices of e are colored by at least min{c,|e|} distinct colors. The hypergraph G is t-intersecting if every two edges of G have at least t vertices in common. We ask: for fixed c >= 2 and t >= 1, what is the minimum number of colors that is sufficient to c-strong color any t-intersecting hypergraphs? The purpose of this note is to answer the question for some values of t and c and, more importantly, to describe the settings for which the question is still open. We show that when t <= c-2, no finite number of colors is sufficient to c-strong color all t-intersecting hypergraphs. It is still unknown whether a finite number of colors suffices for the same task when t = c-1 and c > 2. In the last case, when t >= c, we show with a probabilistic argument that a finite number of colors is sufficient to c-strong color all t-intersecting hypergraphs, but a large gap still remains between the best upper and lower bounds on this number.

Recommendations

• On the \(c\)-strong chromatic number of \(t\)-intersecting hypergraphs
• Coloring 2-intersecting hypergraphs
• On the strong chromatic number of random hypergraphs
• On the number of edges in hypergraphs critical with respect to strong colourings
• Approximation and Online Algorithms

Cites work

• scientific article; zbMATH DE number 487720 (Why is no real title available?)
• On the \(c\)-strong chromatic number of \(t\)-intersecting hypergraphs
• On the hardness of approximating minimum vertex cover
• On the measure of intersecting families, uniqueness and stability

Cited in

(6)

• Semi-strong chromatic number of a graph
• On the \(c\)-strong chromatic number of \(t\)-intersecting hypergraphs
• Coloring hypergraphs with bounded cardinalities of edge intersections
• On \(r\)-dynamic coloring of graphs
• scientific article; zbMATH DE number 3922703 (Why is no real title available?)
• Coloring 2-intersecting hypergraphs

This page was built for publication: Semi-strong colouring of intersecting hypergraphs

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