good edge labeling, edge labeling

Good edge labeling and girth ★★

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.

Posted by DOT
updated September 15th, 2012

Question What is the maximum edge density of a graph which has a good edge labeling?

We say that a graph is good-edge-labeling critical, if it has no good edge labeling, but every proper subgraph has a good edge labeling.

Conjecture For every $c<4$ , there is only a finite number of good-edge-labeling critical graphs with average degree less than $c$ .

Posted by DOT
updated February 16th, 2013