# 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

## Access Full Article

top## Abstract

top## How to cite

topRahul 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] 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] N. Alon and J. Spencer, The Probabilistic Method (John Wiley, 2000). Zbl0996.05001
- [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] 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. Zbl0507.65027
- [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). Zbl0849.68039
- [8] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Metody Diskret. Analys. (1964) 25-30.

## Citations in EuDML Documents

top## NotesEmbed ?

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