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

Abstract

top
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.

How to cite

top

Juan 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. [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. [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. [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. [4] T. Jiang, Edge-colorings with no Large Polychromatic Stars, Graphs and Combinatorics 18 (2002) 303-308, doi: 10.1007/s003730200022. Zbl0991.05044
  5. [5] J.J. Montellano-Ballesteros, On Totally Multicolored Stars, to appear J. Graph Theory. 
  6. [6] J.J. Montellano-Ballesteros and V. Neumann-Lara, An Anti-Ramsey Theorem, Combinatorica 22 (2002) 445-449, doi: 10.1007/s004930200023. 
  7. [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. [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

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.