Unsolved Problems

How to contact me.
Several people have asked me about unsolved problems. I will take the easy way out: see the list of 50 problems in Bondy and Murty. You can now see the list as it originally appeard in the the text, Graph Theory with Applications.
December 2007: I have now received a copy of the new text, GTM 244. and the authors revisit these unsolved problems in Appendix A, and have increased the number of unsolved problems to 100.

Some of these problems have been solved (and thus the title is slightly incorrect) and I won't claim to be familiar with all current results. If you find that one of them has been solved (or even that some reasonable progress has been made), please e-mail me. (How to contact me.) If I receive comments on these new problems, I will of course post those that seem suitable (and, at that point, I would presumably post the problem to which the comment refers). Note, however, the publisher does have a site for the text, http://blogs.springer.com/bondyandmurty/, and it would seem reasonable that one should post comments there. Also, I'm not giving you all of the references in Bondy and Murty or the new text Bondy and Murty 2007. You should get yourself a copy of the new text (and the old text, if you can find it).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Problems 26-56. Problems 57-61. New Problems from GTM 244.
Problems number above 50 on my list are from sources other than the 1976 Bondy and Murty text.

Comments on Problems from the 2007 text will be placed in: New Problems from GTM 244 as I receive them. If a problem is in both texts, I will try to cross-reference, by placing a [red] number after the statement of the problem for the 2007 numbering, and a [green] number for the 1976 numbering.


Bojan Mohar lists some additional graph theoretic problems.
1. 1. The reconstruction conjecture. [1] (S.M. Ulam, 1960; P.J. Kelly, 1942)
2. A graph G is embeddable in a graph H if G is isomorphic to a subgraph of H. Characterise the graphs embeddable in the k-cube. (V.V. Firsov, 1965)
3. Prove: Every 4-regular simple graph contains a 3-regular subgraph. (N. Sauer, 1973)

Conjecture 3 was proved in 1985 by L. Zhang: Every 4-regular simple graph contains a 3-regular subgraph, J. of Changsha Railway Institute 1 (1985), 130-154.

Communicated to me (November 1996) by: Rob Pratt, Department of Mathematics, The University of North Carolina at Chapel Hill, CB# 3250, 331 Phillips Hall, Chapel Hill, NC 27599-3250 (rpratt@math.unc.edu)

Julio Subocz notes that this is also called Berge's conjecure or the Berge-Sauer conjecture and, in a conference in Lisboa (November 1995), Y. H. Hamidoune cited a proof (approximately 65 pages) by Taskinov of the conjecture.

Yair Caro: Solved by Taskinov in 1982 and the proof is not 65 pages.
V.A.Taskinov, Three regular parts of four regular graphs. Math. Notes 36(1984), 612-623 .

Alon + Kallai + Friedland have several extensions.

Taskinov also wrote an earlier paper:
V.A.Taskinov, Regular subgraphs of regular graphs. Sov.Math.Dokl.26(1982), 37-38 .
In this paper he proved the following : Let 0<k<r be positive odd integers. Then every r-regular graph contains a k-regular subgraph (Here, the graph need not be simple).

1. Zhang, Li Min, 4-regular graphs without 3-regular subgraphs. Graph theory and its applications: East and West( Jinan, 1986), 691--699, Ann. New York Acad. Sci, Volume 576. New York Acad. Sci., New York, 1989.

2. Tashkinov, V. A.3-regular subgraphs of 4-regular graphs. (Russian) Mat. Zametki 36(1984), no. 2, 239--259.

4. Prove: If k<2, there exists no graph with the property that every pair of vertices is connected by a unique path of length k. (A. Kotzig, 1974)
Kotzig verified his conjecture for k<9.

Communicated by Yair Caro:
Yuansheng Yang, Jianhua Lin, Chunli Wang,and Kaifeng Li. On Kotzig's conjecture concerning graphs with a unique regular path-connectivity. Discrete Mathematics 211(2000), 287-298.
Abstract: Kotzig (see Bondy and Murty, Graph Theory with Applications, North-Holland, Amsterdam, 1976) conjectured that there exists no graph with the property that every pair of vertices is connected by a unique path of length k,k<2. Kotzig (Graph Theory and Related Topics, Academic Press, New York, 1979, pp. 358-367) has proved this conjecture for 2<k<9. Xing and Hu (Discrete Mathematics 135(1994), 387-393) have proved it for k>11. Here we prove this conjecture for the remaining cases k=9,10,11.

Roland Häggkvist raises a question about one of the steps in the Xing and Hu article. (click here if you want to read the details) Perhaps the problem is still open.
5. Prove: Every connected graph G on n vertices is the union of at most [(n+1)/2] edge-disjoint paths. [7] (T. Gallai, 1962)
See Lovász (1968).

Yair Caro: L.Pyber, JCTB 66(1996), proved that the edges of every connected graph on n vertices can be covered by at most n/2 + O(n3/4) paths.

Communicated by Yair Caro:
Nathaniel Dean and Mekkia Kouider. Gallai's conjecture for disconnected graphs. Discrete Mathematics 213(2000), 43-54.
Abstract: The path number p(G) of a graph G is the minimum number of paths needed to partition the edge set of G. Gallai conjectured that p(G)<=(n+1)/2 for every connected graph G of order n. Because of the graph consisting of disjoint triangles, the best one could hope for in the disconnected case is p(G)<=2n/3. We prove the sharper result that p(G)<=u/2+2g/3 where u is the number of odd vertices and g is the number of nonisolated even vertices.

Communicated by Yair Caro:
Fan Genghua. Subgraph coverings and edge switchings. JCTB 84(2002), 54-83.
Abstract: By using the so-defined circuit/path transformations together with an edge-switching method, the following conjectures were proved in this paper.
(i) The edges of a connected graph on n vertices can be covered by at most ceiling(n/2) paths, which was conjectured by Chung.
(ii) The edges of a 2-connected graph on n vertices can be covered by at most ceiling((2n-1)/3) circuits, which was conjectured by Bondy.
An immediate consequence of (ii) is a theorem of Pyber that the edges of a graph on n vertices can be covered in at most n-1 edges and circuits, which was conjectured by Erdös, Goodman and Pósa.
6. Prove: Every 2-edge-connected simple graph G on n vertices is the union of n-1 cycles. (P. Erdös, A.W. Goodman, L. Pósa, 1966)

See the comment for Question 5, above.
7. Prove: If G is a simple block on n vertices with at least n/2+k vertices of degree at least k, then G has a cycle of length at least 2k. (D.R. Woodall, 1975)

Hao Li has essentially solved this one. He gets a cycle of length at least 2k-13 if G is not hamiltonian. Abstract. (Communicated to me by Galen E. Turner III.)
8. Let f(m,n) be the maximum possible number of edges in a simple graph on n vertices which contains no m-cycle.
If it known that f(m,n) = [n2/4] if m is odd and 2m<n+4; and
f(m,n) = (n-m+2)(n-m+1)/2 + (m-1)(m-2)/2 if 2m>n+2.
Determine f(m,n) in the remaining cases.

Yair Caro: f(4,n) essentially solved recently by Furedi.
Zoltan Furedi, On the number of edges of quadrilateral-free graphs. JCT-B 68(1996), 1-6.
9. Let f(n) be the maximum possible number of edges in a simple graph on n vertices which contains no 3-regular subgraph. Determine f(n) (P. Erdös and N. Sauer, 1974).
Since there is a constant c such that every simple graph with at least cn8/5 edges contains the 3-cube (P. Erdös and M. Simonovits, 1970), clearly f(n)<cn8/5.

Yair Caro: The best known lower bounds are given in the following paper:

L.Pyber , V.Rodel , E.Szemeredi, Dense graphs without 3-regular subgraphs, JCTB 63(1995), 41-54 .

There, reference to an earlier work of Pyber is also given.

Julio Subocz: We relax the condition 3-regular subgraph, in the form: Let us call a graph 3-sum-0 if the degrees are multiples of 3. I think that this idea is due to Alon-Kallai-Friedland, Every four-regular graph plus an edge contains a three regular subgraph, J.Comb.Th.(B) 37(1984), 92-93.

Let g(n) be the maximum possible number of edges in a simple graph of n vertices which contains no 3-sum-0-subgraph. Then
g(4) = 5, g(5) = 8, g(6) = 10, g(7) = 13, but g(n) = 2n, for all n >= 8.
This was obtained with the aid of a computer program.

Julio C. Subocz G., Some Values of Olson's Constant. Proceedings of the VIII Jornadas de Teoría de Grafos. Cumaná, Venezuela. (1998) To appear.
10. Determine which simple graphs G on n vertices have exactly one cycle of each possible length k, 3 <= k <= n (R. Entringer, 1973).

Yair Caro:
  1. There are only seven known UPC-graphs (unipancyclic graphs) having respectively 3, 5, 8, 8, 14, 14, 14 vertices (Entringer).
  2. It is proved that there are only four outerplanar UPC-graphs having 3, 5, 8, 8 vertices respectively.
  3. It is conjectured that the above 7 graphs are the only UPC-graphs.
  4. Essentially there was no progress since 1986 !!
The only available papers on the subject so far are :
11. Let f(n) be the maximum possible number of edges in a graph on n vertices in which no two cycles have the same length. Determine f(n) (P. Erdös, 1975)

Using Math reviews, I found:
94i:05048 05C35
Lai, Chun Hui. On the size of graphs with all cycle having distinct length. (English. English summary) Discrete Math. 122(1993), no. 1-3, pages 363-364.

Summary: "Let $f(n)$ be the maximum number of edges in a graph on $n$ vertices in which no two cycles have the same length. In 1975, Erdos raised the question of determining $f(n)$ [see J. A. Bondy and U. S. R. Murty, Graph theory with applications, Elsevier, New York, 1976; MR 54 #117]. We prove that for $n\geq 36·5t\sp 2-4·5t+1$ one has $f(n)\geq n+9t-1$. We conjecture that $\liminf (f(n)-n)/\sqrt n\leq\sqrt 3$."

96h:05121 05C38 (05C35)
Lai, Chun Hui(PRC-ZZTC), The number of edges of graphs in which all cycles have different lengths.(Chinese. Chinese summary) Zhangzhou Shiyuan Xuebao (Ziran Kexue Ban) 8(1994), no. 4, pages 30-34.

In 1975, P. Erdos proposed the problem of determining the maximum number $f(n)$ of edges in a simple graph of $n$ vertices in which any two cycles are of different lengths. The present paper proves that $ f(n) ≥ n+19t-1$ for $t=360q+7 (q \ge 1)$ and $n ≥ \tfrac{1381}{9}t\sp 2+\tfrac {26}{45}t+\tfrac{98}{45}$. Consequently, $$\liminf\sb {n \to \infty} {f(n)-n \over \sqrt n} ≥ \sqrt {2 + {487 \over 1381}} \approx 1.53, $$ which is better than the previous bounds $\sqrt 2 \approx 1.41$ [Y. B. Shi, Discrete Math. 71 (1988), no. 1, 57--71; MR 89i:05169] and $\sqrt{2+{16 \over 73}} \approx 1.49$ [C. H. Lai, Discrete Math. 122 (1993), no. 1-3, 363--364; MR 94i:05048].

From Yair Caro:
E. Boros, Y. Caro, Z.Furedi and R.Yuster: Covering non-uniform hypergraphs, Journal of Combinatorial Theory, Series B 82(2001), 270-284.
The authors prove f(n) ≤ n + 1.98 sqrt(n) (this is a part of a much more general Turan-type problem considered). A lower bound due to Lai and other shows f(n) ≥ n + sqrt(2n).

See also:
Chunhui Lai, Graphs without repeated cycle lengths. Australasian Journal of Combinatorics 27(2003), 101 - 105.
In this paper, it is proved that f(n) ≥ n+36t for t=1260r+169, (r ≥ 1) and n ≥ 540t2+(175811t+7989)/2. Consequently, $\liminf\sb {n \to \infty} {f(n)-n \over \sqrt n} ≥ \sqrt {2 + {2 \over 5}}.$ We make the following conjecture:


Conjecture. $$\lim_{n \rightarrow \infty} {f(n)-n\over \sqrt n}=\sqrt {2.4}.$$

From Lai Chunhui:
Let f2(n) be the maximum number of edges in a 2-connected graph on n vertices in which no two cycles have the same length. In 2001, E. Boros, Y. Caro, Z. F\"uredi and R. Yuster [Covering non-uniform hypergraphs, Journal of Combinatorial Theory, Series B 82(2001), 270-284.] improved this lower bound significantly:
f2(n) ≥ n + sqrt{n} - O(n9/20).
and conjectured that
\ $\lim \frac{f2 (n)-n}{\sqrt{n}}=1$.
It is easy to see that this Conjecture implies the (difficult) upper bound in the Erdos Turan Theorem (see [E. Boros, Y. Caro, Z. Füredi and R. Yuster, 2001]).
12. Prove: If G is a simple graph on n vertices and the number of edges of G is greater than n(k-1)/2, then G contains every tree with k edges (P. Erdös and V. Sós, 1963).
Erdös and Gallai proved that every such graph contains a path of length k.

Yair Caro: There are many partial results obtained in the last 10 years or so. The most notable are :
  1. The conjectured bound holds true if G is C4-free.
    J.F.Scale and M.Wozniak JCT_B 70(1997), 367-372 (extending an earlier result of Barndt and Dobson).
  2. The conjecture is true for every tree on k vertices having a vertex adjacent to at least (k-2)/2 leaves.
    Sidorenko, Combinatorica 9(1989), 207-215.
13. (Solved) Find a (6,5)-cage.
An (m,n)-cage is an m-regular graph with girth n and, subject to this, with the least possible number of vertices.
The Petersen graph is a (3,5)-cage and has 10 vertices.
The Heawood graph is a (3,6)-cage and has 14 vertices.
The Mcgee graph is a (3,7)-cage and has 24 vertices.
The Tutte-Coxeter graph is a (3,8)-cage and has 30 vertices.
The Robertson graph is a (4,5)-cage and has 19 vertices.
The (4,6)-cage has 26 vertices.
The Robertson-Wegner graph is a (5,5)-cage and 30 vertices.


Markus Meringer sent me the following information.

M. O'Keefe and P. K. Wong, A smallest graph of girth 5 and valency 6. J. Combinatorical Theory Ser B 26(1979) 145-149.

The (6,5)-Cage has 40 vertices and the uniqueness was also proved by Wong.

A good paper on open and solved cage-problems is

P.K. Wong, Cages-A Survey,, JGT, Vol.6 (1982) 1-22

Newer results can be found on Gordon Royle's www-Page http://www.cs.uwa.edu.au/~gordon/cages/allcages.html

14. The bandwidth of a matrix M=(mi,j) is the maximum value of |i-j| such that mi,j is non-zero. The bandwidth of a graph G is the minimum bandwidth among adjacency matrices of graphs isomorphic to G. Find bounds for the bandwidth of a graph (L.H. Harper, 1964).
The bandwidth of the k-cube has been determined by Harper (1966). See also: Chvátalová (1975).

From James R. Lee:
A large amount of progress has been made in recent years. The most promising direction seems to be to relate the bandwidth of a graph to its local density, which is the least D such that every ball of radius r in G has at most rD points, i.e. |B(v,r)| ≤ rD for all v, r, and where the ball is taken in the shortest path metric of G. It is easy to see that D is a lower bound on the bandwidth bw(G). There are some graphs on n vertices with constant density which have bandwith log(n). Thus the gap between bw(G) and D(G) is at least log(n). It is conjectured (by many people, most recently probably by Nati Linial in his talk at the last ICM) that the gap is at mostlog(n), i.e. bw(G) = O(D(G) logn) for any graph. No progress was made until Feige (2000) proved that the gap is at most polylog, i.e. bw(G) = O(D(G) log3.5(n) using embeddings of the graph in euclidean space.
The question is even wide open for trees. Fan Chung (1988) proved that the gap is at least log(n) for certain trees. Gupta (2001) showed that it is most log2.5(n).

U. Feige, Approximating the bandwidth via volume respecting embeddings, Journal of Computer and System Sciences 60(2000), 510-529.
F.R.K. Chung, Labelings of graphs, Selected topics in graph theory, 3, Academic Press 1988, 151-168
Anupam Gupta, Improved bandwidth approximation for trees and chordal graphs, Journal of Algorithms 40(2001), 24-36.
15. A simple graph G on m edges is graceful if there is a labelling l of its vertices with distinct integers from the set {0,1,2,...,m}, so that the induced edge labelling l' defined by l'(uv)=|l(u)-l(v)| assigns each edge a different label. Characterise the graceful graphs (S. Golomb, 1972).
In particular, it has been conjectured that every tree is graceful (A. Rosa, 1966).
16. Solved by Göbel and Jagers, 1976. (Conjecture was false.)
17. Let u and v be vertices in a graph G. Denote the minimum number of vertices whose deletion destroys all (u,v)-paths of length at most n by an, and the maximum number of all internally-disjoint (u,v)-paths of length at most n by bn. Let f(n) denote the maximum possible value of an /bn. Determine f(n) (V. Neumann, 1974).
L. Lovász has conjectured that f(n) is at most the square root of n.
It is known that sqrt(n/2) <= f(n) <= n/2.

Solved by: Stephanie Boyles and G. Exoo. A Counterexample to a Conjecture on Paths of Bounded Length. J. Graph Theory 6(1982), 205-209. In effect, they showed that f(n) is linear.
18. Prove that every 3-regular 3-connected bipartite planar graph is hamiltonian (Barnette, 1970).
P. Goodey has verified this conjecture for plane graphs whose faces are all of degee four or six. Note that if the planarity condition is dropped, the Horton graph demonstrates that the conjecture is no longer valid.

In progress: Tomas Feder and Carlos Sudi have written a partial solution (link sent to me by G.R.). I've been informed (thank you to P.H.) that they offer a very nice solution for some cases, but not for all cases.
19. A graphic sequence d is forcibly hamiltonian if every simple graph with degree sequence d is hamiltonian. Characterize the forcibly hamiltonian sequences (C. St. J. A. Nash-Williams, 1970).
20. Prove that every connected vertex-transitive graph has a Hamilton path (L. Lovász, 1968).
L. Babai has verified this conjecture for any graph with a prime number of vertices.
(I seem to remember it also has been proved with the number of vertices the square of a prime and perhaps also for the number of vertices the cube of a prime.)
A graph G is t-tough if, for every vertex cut S, the number of components of G-S is at most |S|/t.
For example, every hamiltonian graph is 1-tough.
A k-factor is a k-regular spanning subgraph.

21(a). Prove that every 2-tough graph is hamiltonian (Chvátal, 1971).
C. Thomassen has obtained an example of a (3/2)-tough non-hamiltonian graph.

Hajo Broersma sent the following e-mail message (19 June 1997):

Dear colleague,

Since you either attended the EIDMA Workshop on Hamiltonicity of 2-Tough Graphs or at least were invited to do so, we guess you are interested in the fact that we have refuted the conjecture that every 2-tough graph is hamiltonian. In fact, we found examples of t-tough nontraceable graphs for arbitrary t<9/4. We already wrote a preliminary paper. If you are interested in receiving a postscript file, just let us know.

Best wishes,
Doug Bauer, Hajo Broersma, Henk Jan Veldman.

Abstract

21(b). It was conjectured that every (3/2)-tough graph has a 2-factor (Chvátal, 1971). A recent e-mail message from Erik Engbers, a student at U. Twente, points out that this was settled in the negative by a result of H. Enomoto, B. Jackson and P.Katerinis. The following theorem appears in their article:

Let k>=1. For any positive real number s, there exists a (k-s)-tough graph G with k|V(G)| even and |V(G)| >= (k+1) and which has no k-factor.

H. Enomoto, B. Jackson and P.Katerinis. Toughness and the existence of k-factors, Journal of Graph Theory, 9(1985), 87-95.
The following interesting result was proven by Enomoto (1985):

If G is k-tough, |V(G)|>=k+1 and k|V(G)| is even, then G has a k-factor. This result is generalized in several ways by C. Chen and P. Katerinis.

I thank Mr. Engbers for helping make my file more current. Jan van der Heuvel wrote his Ph.D. Thesis on toughness problems. I should have remembered the J-E-K result from there.
The binding number of a graph G is defined by
bind(G) = minimum |N(S)|/|S|,
where the minimum is over non-empty, proper subsets S of V(G), with N(S) not all of V(G).

A simple graph on n vertices is pancyclic if it contains cycles of all lengths, 3,4,...,n.

22(a). Prove that every graph G with bind(G) >= 3/2 contains a triangle (D.R. Woodall, 1973).

22(b). Prove that every graph G with bind(G) >= 3/2 is pancyclic (D.R. Woodall, 1973).

Woodall has shown that G is hamiltonian if bind(G) >= 3/2, and that G contains a triangle if bind(G) >= (1+sqrt(5))/2.

Conjectures 22(a) and 22(b) were proved by R. Shi:

R. Shi. The binding number of a graph and its triangle. Acta Math. Appl. Sinica (English Series), 2 (1985), pp. 79--86.

R. Shi. The binding number of a graph and its circuits. Acta Math. Appl. Sinica (English Series), 2 (1985), pp. 154--160.

R. Shi. The binding number of a graph and its pancyclism. Acta Math. Appl. Sinica (English Series), 3 (1987), pp. 257--269.

See also:

W. Goddard and D. J. Kleitman. A Note on Maximal Triangle-Free Graphs. Journal of Graph Theory, Vol. 17, No. 5 (1993), pp. 629-631.

Communicated to me (July 1997) by: Alexandre Tiskin (tiskin@comlab.ox.ac.uk)
23. Prove that every nonempty regular simple graph contains two disjoint maximal independent sets (C. Payan, 1973).

Yair Caro: I finally got an information concerning problem #23 by Payan. (This was done via GRAPHNET).

Erdos, Payan, Hobbs proved that the conjecture is true for (n-k)-regular graphs when k < -2 + 2sqrt(2n), where |V(G)| = n. Disc. Math. 42(1982), 57-61 (Information from Arthur Hobbs).

In general the conjecture is FALSE. There is a counter-example with 630 vertices and degree 280. This was shown by Payan himself as early as 1978. Disc. Math. 23(1978), 273-277. (Information by Brendan McKay).
The Ramsey number r(k1,...,km) is the minimum integer n such that every m-edge-colouring of Kn contains a complete subgraph on ki vertices, with all edges of colour i, for some i.

F.P. Ramsey. On a problem in formal logic. Proc. London Math. Soc. (2) 30(1930), 264-286.

24. Find the Ramsey number r(3,3,3,3).

It is known that 51 <= r(3,3,3,3) <= 65. [F.R.K. Chung, 1973] [J. Folkman, 1974]

Here are the best known bounds (Stanislaw P Radziszowski in a message to Yair Caro):

[Chung] 51 <= R(3,3,3,3) <= 64 [Sanchez-Flores]

F.R.K. Chung, On the Ramsey Numbers N(3,3,...,3;2), Discrete Mathematics 5(1973), 317-321.
A. Sanchez-Flores, An Improved Bound for Ramsey Number N(3,3,3,3;2), Discrete Mathematics 140(1995), 281-286.
25. For m < n, let f(m,n) denote the least possible number of vertices in a graph which contains no Kn but has the property that in every 2-edge-colouring there is a monochromatic Km.
Folkman (1970) established the existence of such graphs.
Determine bounds for f(m,n).
It is known that
f(3,n)=6 for n >= 7
f(3,6)=8
10 <= f(3,5) <= 18
See also: [R.W. Irving, 1973] [S. Lin, JCTB12]

Klas Markstrom: The folkman number f(3,5) has been determined, f(3,5)= 15. This result and information on bounds for some other folkman numbers is published in:
Konrad Piwakowski, Stanislaw P. Radziszowski and Sebastian Urbanski, Computation of the Folkman number Fe(3,3;5). Journal of Graph Theory 32{1999}, pages 41-49.
Department of Mathematical Sciences
Florida Atlantic University
777 Glades Road
Boca Raton, Florida 33431-0991
USA

Office: Room 286, Science & Engineering
Phone: (561) 297-3350
Fax: (561) 297-2436
URL: http://www.math.fau.edu/locke/unsolved.htm

Last modified January 22, 2001, by S.C. Locke.