ArticleOriginal scientific text

Title

On k-intersection edge colourings

Authors 1, 1, 1

Affiliations

  1. The Institute of Mathematical Sciences, Taramani, Chennai-600113, India

Abstract

We propose the following problem. For some k ≥ 1, a graph G is to be properly edge coloured such that any two adjacent vertices share at most k colours. We call this the k-intersection edge colouring. The minimum number of colours sufficient to guarantee such a colouring is the k-intersection chromatic index and is denoted χ'ₖ(G). Let fₖ be defined by f(Δ)=maxG:Δ(G)=Δ{χ(G)}. We show that fₖ(Δ) = Θ(Δ²/k). We also discuss some open problems.

Keywords

graph theory, k-intersection edge colouring, probabilistic method

Bibliography

  1. N. Alon and B. Mohar, Chromatic number of graph powers, Combinatorics Probability and Computing 11 (2002) 1-10, doi: 10.1017/S0963548301004965.
  2. N. Alon and J. Spencer, The Probabilistic Method (John Wiley, 2000).
  3. A.C. Burris and R.H. Schelp, Vertex-distinguishing proper edge colourings, J. Graph Theory 26 (1997) 70-82, doi: 10.1002/(SICI)1097-0118(199710)26:2<73::AID-JGT2>3.0.CO;2-C
  4. P. Erdös and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, in: Infinite and Finite Sets, 1975.
  5. S.T. McCormick, Optimal approximation of sparse Hessians and its equivalence to a graph colouring problem, Mathematical Programming 26 (1983) 153-171, doi: 10.1007/BF02592052.
  6. M. Molloy and B. Reed, Graph Coloring and the Probabilistic Method (Springer, Algorithms and Combinatorics, 2002).
  7. R. Motwani and P. Raghavan, Randomized Algorithms (Cambridge University Press, 1995).
  8. V.G. Vizing, On an estimate of the chromatic class of a p-graph, Metody Diskret. Analys. (1964) 25-30.
Pages:
411-418
Main language of publication
English
Received
2007-12-03
Accepted
2009-02-14
Published
2009
Exact and natural sciences