For the start of 2005, we have selected some open problems and conjectures that were posed at the Oberwolfach meeting on Graph Theory in January 2005 (click here for the conference photo). Part 2 is about to follow in February/March.

**Conjecture (Stephan Thomasse):** Let
D be a digraph with minimum outdegree *d* and with directed girth *g*.
Then D has a (directed) path of length (*g* - 1)*d*.

This conjecture may be hard to prove since it implies the Caccetta-Haggkvist conjecture [1].

**Conjecture (Caccetta-Haggkvist):** Let
D be a digraph of order *n* in which every vertex has outdegree at least *
d*.
Then D contains a directed cycle of length *g* such that (*g* - 1)*d*
< *n*.

For *g* = 3, this gives the following seemingly simple
problem:

Thomasse [3] can show that there is a path of
length 3*d*/2, and Bill Jackson
has proved *d* + *d'*, where *d'* is the minimum indegree [2].

A graph G is said to be 2-factor hamiltonian if it contains a 2-factor, but
every 2-factor of G is a hamiltonian cycle. Examples of such graphs are K_{4},
K_{5}, K_{3,3 }and the Heawood graph. If G and H are 2-factor
hamiltonian cubic graphs, let L be the graph obtained from their disjoint union
by deleting a vertex from each of them and adding a 3-matching joining the three
vertices of degree 2 in the first graph with those in the second. Then it is
easy to see that L is also 2-factor hamiltonian. We say that L is a *product*
of G and H.

**Conjecture (Bill Jackson et al. [4]):** Let
k be a positive integer and let G be a bipartite k-regular 2-factor hamiltonian
graph. Then k = 2 or 3, and if k = 3, then G is an iterated product of graphs
isomorphic either to K_{3,3} or to the Heawood graph.

The first conclusion of the conjecture (that k = 2 or 3) has been verified in [4]. There is also a related open problem:

**Problem (Bill Jackson et al. [5]):** Let
k be a positive integer and let G be a 2k-regular 2-factor hamiltonian graph.
Then k = 1 or 2, and if k = 2, then G is isomorphic to K_{5}.

**References**

[1] L. Caccetta, R. Haggkvist, On minimal digraphs with given girth, Proc. 9th SE Conf. Comb., Graph Theory and Computing, Congr. Numer. 21 (1978) 181-187.

[2] B. Jackson, Long paths and cycles in oriented graphs, J. Graph Theory 5 (1981) 145-157.

[3] S. Thomasse, private communication (unpublished, 2002).

[4] M. Funk, B. Jackson, D. Labbate, and J Sheehan, 2-factor Hamiltonian graphs, J. Combinatorial Theory (B) 87 (2003) 138-144.

[5] M. Abreu, R. A. Aldred, M. Funk, B. Jackson, D. Labbate, and J Sheehan, Graphs and digraphs with all 2-factors isomorphic, J. Combinatorial Theory (B) 92 (2004) 395-404.

Send comments to Bojan.Mohar@uni-lj.si