Open Problem Garden

Geodesic cycles and Tutte's Theorem ★★

Problem If $G$ is a $3$ -connected finite graph, is there an assignment of lengths $\ell: E(G) \to \mathb R^+$ to the edges of $G$ , such that every $\ell$ -geodesic cycle is peripheral?

Keywords: cycle space; geodesic cycles; peripheral cycles

Posted by Agelos
updated August 4th, 2007

add new comment

covering system

Graph Theory » Coloring » Vertex coloring

Oriented chromatic number of planar graphs ★★

Author(s):

An oriented colouring of an oriented graph is assignment $c$ of colours to the vertices such that no two arcs receive ordered pairs of colours $(c_1,c_2)$ and $(c_2,c_1)$ . It is equivalent to a homomorphism of the digraph onto some tournament of order $k$ .