Good edge labeling and girth (Solved)

Importance: Medium ✭✭
Author(s): Bode-Farzad-Theis
Subject: Graph Theory
» Coloring
» » Labeling
Recomm. for undergrads: no
Posted by: DOT
on: September 13th, 2011
Solved by:
Conjecture   Every graph with large girth has a good edge labeling.

More specifically: there exists a constant $ g $ such that every graph with girth at least $ g $ has a good edge labeling.

Let $ G $ be a finite undirected simple graph. A good edge labeling of $ G $ is an assignment of distinct numbers to the edges such that every cycle has at least two local maxima. (The distinctness of the labels is required only to make the term `local maximum' unambiguous.)

Equivalently, a labeling of the edges is good, if for every pair of distinct vertices $ u,v $, there is at most one increasing path from $ u $ to $ v $.

It is easy to verify that the graphs $ K_3 $ and $ K_{2,3} $ have no good edge labeling. In [ACGH2] an infinite class of graphs without good edge labelings is given. All these graphs have many 4-cycles.

Indeed, no example is known of a graph of girth 5 or more without a good edge labeling. In other words, it may be possible that $ g=5 $ suffices for the conjecture.


*[BFT] M. Bode, B. Farzad, D.O. Theis. Good edge-labelings and graphs with girth at least five.

[ACGH1] J. Araújo, N. Cohen, F. Giroire, F. Havet. Good edge-labelling of graphs. (English summary) LAGOS'09—V Latin-American Algorithms, Graphs and Optimization Symposium, 275–280, Electron. Notes Discrete Math., 35, Elsevier Sci. B. V., Amsterdam, 2009. MathSciNet

[ACGH2] J. Araujo, N. Cohen, F. Giroire, and F. Havet. Good edge-labelling of graphs. Research Report 6934, INRIA, 2009.

[BCP] J-C. Bermond, M. Cosnard, and S. Pérennes. Directed acyclic graphs with unique path property. Technical report 6932, INRIA, May 2009

* indicates original appearance(s) of problem.


Mehrabian, SIAM J Discrete Math, 2012.

link to the resolving paper

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.