On k-intersection edge colourings

Rahul Muthu; N. Narayanan; C.R. Subramanian

Discussiones Mathematicae Graph Theory (2009)

  • Volume: 29, Issue: 2, page 411-418
  • ISSN: 2083-5892

Abstract

top
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 ₖ ( Δ ) = m a x G : Δ ( G ) = Δ χ ' ₖ ( G ) . We show that fₖ(Δ) = Θ(Δ²/k). We also discuss some open problems.

How to cite

top

Rahul Muthu, N. Narayanan, and C.R. Subramanian. "On k-intersection edge colourings." Discussiones Mathematicae Graph Theory 29.2 (2009): 411-418. <http://eudml.org/doc/270823>.

@article{RahulMuthu2009,
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ₖ(Δ) = max_\{G : Δ(G) = Δ\} \{χ^\{\prime \}ₖ(G)\}$. We show that fₖ(Δ) = Θ(Δ²/k). We also discuss some open problems.},
author = {Rahul Muthu, N. Narayanan, C.R. Subramanian},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph theory; k-intersection edge colouring; probabilistic method; -intersection edge colouring},
language = {eng},
number = {2},
pages = {411-418},
title = {On k-intersection edge colourings},
url = {http://eudml.org/doc/270823},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Rahul Muthu
AU - N. Narayanan
AU - C.R. Subramanian
TI - On k-intersection edge colourings
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 2
SP - 411
EP - 418
AB - 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ₖ(Δ) = max_{G : Δ(G) = Δ} {χ^{\prime }ₖ(G)}$. We show that fₖ(Δ) = Θ(Δ²/k). We also discuss some open problems.
LA - eng
KW - graph theory; k-intersection edge colouring; probabilistic method; -intersection edge colouring
UR - http://eudml.org/doc/270823
ER -

References

top
  1. [1] N. Alon and B. Mohar, Chromatic number of graph powers, Combinatorics Probability and Computing 11 (2002) 1-10, doi: 10.1017/S0963548301004965. Zbl0991.05042
  2. [2] N. Alon and J. Spencer, The Probabilistic Method (John Wiley, 2000). Zbl0996.05001
  3. [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 Zbl0886.05068
  4. [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. [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. Zbl0507.65027
  6. [6] M. Molloy and B. Reed, Graph Coloring and the Probabilistic Method (Springer, Algorithms and Combinatorics, 2002). 
  7. [7] R. Motwani and P. Raghavan, Randomized Algorithms (Cambridge University Press, 1995). Zbl0849.68039
  8. [8] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Metody Diskret. Analys. (1964) 25-30. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.