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.
Thomasse [3] can show that there is a path of length 3d/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 K4, K5, K3,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 K3,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 K5.
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
