The paper cited (available at http://orion.math.iastate.edu/axenovic/Papers/Martin_Strong.pdf) only resolves the above conjecture for graphs G which have maximum degree at least |V(G)|/6.
only partly solved
The paper cited (available at http://orion.math.iastate.edu/axenovic/Papers/Martin_Strong.pdf) only resolves the above conjecture for graphs G which have maximum degree at least |V(G)|/6.