Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Conflict-free colorings of graphs and hypergraphs Probability and Computing
 
research article

Conflict-free colorings of graphs and hypergraphs Probability and Computing

Pach, J.  
•
Tardos, G.
2009
Combinatorics

A colouring of the vertices of a hypergraph H is called conflict-free if each hyperedge E of H contains a vertex of 'unique' colour that does not get repeated in E. The smallest number of colours required for such a colouring is called the conflict-free chromatic number of H, and is denoted by chi(CF)(H). This parameter wits first introduced by Even, Lotker, Ron and Smorodinsky (FOCS 2002) in a geometric setting, in connection with frequency assignment problems for cellular networks. Here we analyse this notion for general hypergraphs. It is shown that chi(CF)(H) <= 1/2 + root 2m + 1/4, for every hypergraph with tit edges, and that this bound is tight. Better bounds of the order of tit 1 It log tit are proved under the assumption that the size of every edge of H is at least 2t - 1, for some t >= 3. Using Lovasz's Local Lemma, the same result holds for hypergraphs in which the size of every edge is at least 2t - 1 and every edge intersects at most tit others. We give efficient polynomial-time algorithms to obtain such colourings.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

S0963548309990290.pdf

Type

Publisher's Version

Version

Published version

Access type

openaccess

Size

171.96 KB

Format

Adobe PDF

Checksum (MD5)

b26b012b103ed88213f7524345990c2c

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés