# An anti-Ramsey theorem on edge-cuts

Juan José Montellano-Ballesteros

Discussiones Mathematicae Graph Theory (2006)

- Volume: 26, Issue: 1, page 19-21
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topJuan José Montellano-Ballesteros. "An anti-Ramsey theorem on edge-cuts." Discussiones Mathematicae Graph Theory 26.1 (2006): 19-21. <http://eudml.org/doc/270597>.

@article{JuanJoséMontellano2006,

abstract = {Let G = (V(G), E(G)) be a connected multigraph and let h(G) be the minimum integer k such that for every edge-colouring of G, using exactly k colours, there is at least one edge-cut of G all of whose edges receive different colours. In this note it is proved that if G has at least 2 vertices and has no bridges, then h(G) = |E(G)| -|V(G)| + 2.},

author = {Juan José Montellano-Ballesteros},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {anti-Ramsey; totally multicoloured; edge-cuts; connected multigraph},

language = {eng},

number = {1},

pages = {19-21},

title = {An anti-Ramsey theorem on edge-cuts},

url = {http://eudml.org/doc/270597},

volume = {26},

year = {2006},

}

TY - JOUR

AU - Juan José Montellano-Ballesteros

TI - An anti-Ramsey theorem on edge-cuts

JO - Discussiones Mathematicae Graph Theory

PY - 2006

VL - 26

IS - 1

SP - 19

EP - 21

AB - Let G = (V(G), E(G)) be a connected multigraph and let h(G) be the minimum integer k such that for every edge-colouring of G, using exactly k colours, there is at least one edge-cut of G all of whose edges receive different colours. In this note it is proved that if G has at least 2 vertices and has no bridges, then h(G) = |E(G)| -|V(G)| + 2.

LA - eng

KW - anti-Ramsey; totally multicoloured; edge-cuts; connected multigraph

UR - http://eudml.org/doc/270597

ER -

## References

top- [1] N. Alon, On a Conjecture of Erdös, Simonovits and Sós Concerning Anti-Ramsey Theorems, J. Graph Theory 7 (1983) 91-94, doi: 10.1002/jgt.3190070112. Zbl0456.05038
- [2] P. Erdös, M. Simonovits and V.T. Sós, Anti-Ramsey Theorems, in: Infinite and finite sets (Keszthely, Hungary 1973), Colloquia Mathematica Societatis János Bolyai, 10, (North-Holland, Amsterdam, 1975) 633-643.
- [3] P. Hell and J.J. Montellano-Ballesteros, Polychromatic Cliques, Discrete Math. 285 (2004) 319-322, doi: 10.1016/j.disc.2004.02.013. Zbl1044.05051
- [4] T. Jiang, Edge-colorings with no Large Polychromatic Stars, Graphs and Combinatorics 18 (2002) 303-308, doi: 10.1007/s003730200022. Zbl0991.05044
- [5] J.J. Montellano-Ballesteros, On Totally Multicolored Stars, to appear J. Graph Theory.
- [6] J.J. Montellano-Ballesteros and V. Neumann-Lara, An Anti-Ramsey Theorem, Combinatorica 22 (2002) 445-449, doi: 10.1007/s004930200023.
- [7] M. Simonovits and V.T. Sós, On Restricted Colourings of Kₙ, Combinatorica 4 (1984) 101-110, doi: 10.1007/BF02579162. Zbl0538.05047
- [8] H. Whitney, Non-separable and planar graphs, Trans. Amer. Math. Soc. 34 (1932) 339-362, doi: 10.1090/S0002-9947-1932-1501641-2. Zbl58.0608.01