Hostname: page-component-f554764f5-nwwvg Total loading time: 0 Render date: 2025-04-09T01:10:51.600Z Has data issue: false hasContentIssue false
  • English
  • Français

Conflict-Free Colourings of Graphs and Hypergraphs

Published online by Cambridge University Press: 01 September 2009

JÁNOS PACH
Affiliation:
EPFL-SB-IMB-DCG, CH-1015 Lausanne, Switzerland and Department of Computer Science, City College, 138th Street at Convent Avenue, NY, NY 10031, USA (e-mail: pach@cims.nyu.edu)
GÁBOR TARDOS
Affiliation:
School of Computing Science, Simon Fraser University, 8888 University Drive, Burnaby, BC, V5A 1S6, Canada and Rényi Institute, 13–15 Reáltanoda utca Budapest, Hungary (e-mail: tardos@cs.sfu.edu)

Abstract

A colouring of the vertices of a hypergraphH is calledconflict-free if each hyperedgeE ofH contains a vertex of ‘unique’ colour that does not get repeated inE. The smallest number of colours required for such a colouring is called theconflict-free chromatic number ofH, and is denoted by χCF(H). This parameter was first introduced by Even, Lotker, Ron and Smorodinsky (FOCS 2002) in ageometric setting, in connection with frequency assignment problems for cellular networks. Here we analyse this notion for general hypergraphs. It is shown that, for every hypergraph withm edges, and that this bound is tight. Better bounds of the order ofm1/t logm are proved under the assumption that the size of every edge ofH is at least 2t − 1, for somet ≥ 3. Using Lovász'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 mostm others. We give efficient polynomial-time algorithms to obtain such colourings.

Our machinery can also be applied to the hypergraphs induced by the neighbourhoods of the vertices of a graph. It turns out that in this case we need far fewer colours. For example, it is shown that the vertices of any graphG with maximum degree Δ can be coloured with log2+ε Δ colours, so that the neighbourhood of every vertex contains a point of ‘unique’ colour. We give an efficient deterministic algorithm to find such a colouring, based on a randomized algorithmic version of the Lovász Local Lemma, suggested by Beck, Molloy and Reed. To achieve this, we need to (1) correct a small error in the Molloy–Reed approach, (2) restate and re-prove their result in adeterministic form.

Type
Paper
Copyright
Copyright © Cambridge University Press 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

References

[1]Ajwani,D.,Elbassioni,K.,Govindarajan,S. andRay,S. (2007) Conflict-free coloring for rectangle ranges usingO(n0.382) colors. InProc. 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 181–187.Google Scholar
[2]Alon,N. (1991)A parallel algorithmic version of the local lemma.Random Struct. Alg.2367–378.CrossRefGoogle Scholar
[3]Alon,N. andSmorodinsky,S. (2006) Conflict-free colorings of shallow discs. In22nd Ann. ACM Symposium on Computational Geometry (SoCG), pp. 41–43.CrossRefGoogle Scholar
[4]Alon,N. andSpencer,J. (2000)The Probabilistic Method,2nd edn,Wiley,New York.CrossRefGoogle Scholar
[5]Aardal,K.,van Hoesel,S.,Koster,A.,Mannino,C. andSassano,A. (2003)Models and solution techniques for frequency assignment problems.4OR1261–317.Google Scholar
[6]Bar-Noy,A.,Cheilaris,P. andSmorodinsky,S. (2008)Deterministic conflict-free coloring for intervals: From offline to online.ACM Trans. Alg.4#44.Google Scholar
[7]Beck,J. (1991)An algorithmic approach to the Lovász local lemma.Random Struct. Alg.2343–365.CrossRefGoogle Scholar
[8]Behzad,M. (1971) The total chromatic number of a graph: A survey. InCombinatorial Mathematics and its Applications (Oxford 1969),Academic Press,London, pp.1–8.Google Scholar
[9]Cheilaris,P. (2008) Conflict-free coloring. PhD thesis, City University of New York.Google Scholar
[10]Chen,K. (2006) How to play a coloring game against a color-blind adversary. InProc. 22nd Annual ACM Symposium on Computational Geometry (SoCG), pp. 44–51.CrossRefGoogle Scholar
[11]Chen,K.,Fiat,A.,Kaplan,H.,Levy,M.,Matoušek,J.,Mossel,E.,Pach,J.,Sharir,M.,Smorodinsky,S.,Wagner,U. andWelzl,E. (2006)Online conflict-free coloring for intervals.SIAM J. Comput.361342–1359.CrossRefGoogle Scholar
[12]Czumaj,A. andScheideler,C. (2000) A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems. InProc. 32nd Annual ACM Symposium on Theory of Computing,ACM,New York, pp.38–47.Google Scholar
[13]Czumaj,A. andScheideler,C. (2000)Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lovász local lemma. InProc. 9th International Conference ‘Random Structures and Algorithms’ (Poznan 1999),Random Struct. Alg.17213–237.3.0.CO;2-Y>CrossRefGoogle Scholar
[14]Diestel,R. (2005)Graph Theory,3rd edn, Vol. 173 ofGraduate Texts in Mathematics,Springer,Berlin.Google Scholar
[15]Erdős,P. andLovász,L. (1975) Problems and results on 3-chromatic hypergraphs and some related questions. InInfinite and Finite Sets (to Paul Erdős on his 60th birthday), Vol. II (Hajnal,A. et al. , eds),North-Holland,Amsterdam, pp.609–627.Google Scholar
[16]Even,G.,Lotker,Z.,Ron,D. andSmorodinsky,S. (2003)Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks.SIAM J. Comput.3394–136.CrossRefGoogle Scholar
[17]Har-Peled,S. andSmorodinsky,S. (2005)Conflict-free coloring of points and simple regions in the plane.Discrete Comput. Geometry3447–70.CrossRefGoogle Scholar
[18]Hind,H.,Molloy,M. andReed,B. (1997)Colouring a graph frugally.Combinatorica17469–482.CrossRefGoogle Scholar
[19]Leighton,T.,Lu.,C.-J.,Rao,S. andSrinivasan,A. (2001)New algorithmic aspects of the local lemma with applications to routing and partitioning.SIAM J. Comput.31626–641.CrossRefGoogle Scholar
[20]Molloy,M. andReed,B. (1998) Further algorithmic aspects of the local lemma. InProc. 30th Annual ACM Symposium on Theory of Computing, pp. 524–529.CrossRefGoogle Scholar
[21]Molloy,M. andReed,B. (2002)Graph Colouring and the Probabilistic Method, Vol. 23 ofAlgorithms and Combinatorics,Springer,Berlin.CrossRefGoogle Scholar
[22]Molloy,M. andSalavatipour,M. R. (2005)A bound on the chromatic number of the square of a planar graph.J. Combin. Theory Ser. B94189–213.CrossRefGoogle Scholar
[23]Moser,R. A constructive proof of the Lovász Local Lemma. InProc. 41st Annual ACM Symposium on Theory of Computing, pp. 343–350.Google Scholar
[24]Moser,R. andTardos,G. (2009) A constructive proof of the general Lovász Local Lemma. arXiv:0903.0544v3.CrossRefGoogle Scholar
[25]Pach,J. andTóth,G. (2003) Conflict-free colorings. InDiscrete and Computational Geometry, Vol. 25 ofAlgorithms and Combinatorics,Springer,Berlin, pp.665–671.CrossRefGoogle Scholar
[26]Smorodinsky,S. (2007)On the chromatic number of some geometric hypergraphs.SIAM J. Discrete Math.21676–687.CrossRefGoogle Scholar
[27]Wegner,G. (1977) Graphs with given diameter and a coloring problem. Technical Report, University of Dortmund.Google Scholar
[28]Woldar,A. (2002) Rainbow graphs. InCodes and Designs (Columbus 2000), Vol. 10 ofOhio State Univ. Math. Res. Inst. Publ.,de Gruyter,Berlin, pp.313–322.CrossRefGoogle Scholar