Hostname: page-component-745bb68f8f-g4j75 Total loading time: 0 Render date: 2025-02-06T16:05:45.120Z Has data issue: false hasContentIssue false
  • English
  • Français

Semi-Strong Colouring of Intersecting Hypergraphs

Published online by Cambridge University Press:  24 October 2013

ERIC BLAIS ,
AMIT WEINSTEIN  and
YUICHI YOSHIDA
ERIC BLAIS
Affiliation:
Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA 02139, USA (e-mail: eblais@csail.mit.edu)
AMIT WEINSTEIN
Affiliation:
Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel (e-mail: amitw@tau.ac.il)
YUICHI YOSHIDA
Affiliation:
National Institute of Informatics, Tokyo 101-8430, Japan and Preferred Infrastructure, Inc., Tokyo 113-0033, Japan (e-mail: yyoshida@nii.ac.jp)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

For any c ≥ 2, a c-strong colouring of the hypergraph G is an assignment of colours to the vertices of G such that, for every edge e of G, the vertices of e are coloured by at least min{c,|e|} distinct colours. The hypergraph G is t-intersecting if every two edges of G have at least t vertices in common.

A natural variant of a question of Erdős and Lovász is: For fixed c ≥ 2 and t ≥ 1, what is the minimum number of colours that is sufficient to c-strong colour any t-intersecting hypergraphs? The purpose of this note is to describe some open problems related to this question.

Keywords

Primary 05C15Secondary 05D40
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 1 , January 2014 , pp. 1 - 7
Copyright
Copyright © Cambridge University Press 2013 

References

[1]Alon, N. (2013) Paul Erdős and probabilistic reasoning. In Erdős Centennial, Vol. 25 of Bolyai Society Mathematical Studies (Lovász, L., Ruzsa, I. and Sós, V., eds), Springer, pp. 11–33.Google Scholar
[2]Blais, E., Weinstein, A. and Yoshida, Y. (2012) Partially symmetric functions are efficiently isomorphism-testable. In Proc. 53rd Annual IEEE Symposium on Foundations of Computer Science: FOCS, IEEE Computer Society, pp. 551–560.Google Scholar
[3]Chung, P. N. (2013) On the c-strong chromatic number of t-intersecting hypergraphs. Discrete Math. 313 1063–1069.Google Scholar
[4]Dinur, I. and Safra, S. (2005) On the hardness of approximating minimum vertex cover. Ann. of Math. 162 439–485.Google Scholar
[5]Erdős, P. and Lovász, L. (1973) Problems and results on 3-chromatic hypergraphs and some related questions. Coll. Math. Soc. J. Bolyai 10 609–627.Google Scholar
[6]Friedgut, E. (2008) On the measure of intersecting families, uniqueness and stability. Combinatorica 28 503–528.Google Scholar
[7]Jensen, T. R. and Toft, B. (1994) Graph Coloring Problems, Wiley.Google Scholar
[8]Lovász, L. (1993) Combinatorial Problems and Exercises, second edition, AMS.Google Scholar
[9]Molloy, M. and Reed, B. (2001) Graph Colouring and the Probabilistic Method, Springer.Google Scholar