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.

Note, in the new version of Bondy and Murty's text, GTM 244, 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 of this webpage 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.) Please note that I much prefer comments sent by e-mail to those sent by telehone, as I very frequently have trouble deciphiring messages left on my telephone.

If I receive comments on the 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.

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

3. Prove: Every 4-regular simple graph contains a 3-regular subgraph. (N. Sauer, 1973)

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,

Alon + Kallai + Friedland have several extensions.

Taskinov also wrote an earlier paper:

V.A.Taskinov,

In this paper he proved the following : Let

1. Zhang, Li Min,

2. Tashkinov, V. A.

4. Prove: If

Kotzig verified his conjecture for

Communicated by Yair Caro:

Yuansheng Yang, Jianhua Lin, Chunli Wang,and Kaifeng Li.

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

See Lovász (1968).

Yair Caro: L.Pyber,

Communicated by Yair Caro:

Nathaniel Dean and Mekkia Kouider.

Communicated by Yair Caro:

Fan Genghua.

(i) The edges of a connected graph on

(ii) The edges of a 2-connected graph on

An immediate consequence of (ii) is a theorem of Pyber that the edges of a graph on

6. Prove: Every 2-edge-connected simple graph

See the comment for Question 5, above.

7. Prove: If

Hao Li has essentially solved this one. He gets a cycle of length at least

8. Let

If it known that

Determine

Yair Caro: f(4,n) essentially solved recently by Furedi.

Zoltan Furedi,

9. Let

Since there is a constant

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

L.Pyber , V.Rodel , E.Szemeredi,

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

Let

Julio C. Subocz G.,

10. Determine which simple graphs

Yair Caro:

- There are only
seven known UPC-graphs (
*unipancyclic graphs*) having respectively 3, 5, 8, 8, 14, 14, 14 vertices (Entringer). - It is proved that there are only four outerplanar UPC-graphs having 3, 5, 8, 8 vertices respectively.
- It is conjectured that the above 7 graphs are the only UPC-graphs.
- Essentially there was no progress since 1986 !!

- Shi, Y.B., Yap, H.P,. and Teo, S.K.,
*On uniquely r-pancyclic graphs*,**Graph Theory and Its Applications: East and West**, (Jinan, 1986), 487-499, Ann. New York Acad. Sci., 576, New York Acad. Sci. New York, 1989. MR 93d:05088 - Shi, Y.B.,
*Some theorems of uniquely pancyclic graphs*,**Discrete Math. 59**(1986), 167-180. MR 87j:05103 - from
Klas Markstrom:
*A note on uniquely pancyclic graphs*, technical report No 8 2000, Department of Mathematics, Umeå University, submitted to Discrete Mathematics.-
I have shown that there
are no such graphs on less than 56 vertices other than the seven previously
found. The proof is basically a computer search. I also give some bounds
for the number of edges in a uniquely pancyclic graph.

Communicated by Chunhui Lai:

Carol T. Zamfirescu, "We introduce the class of (2)-pancyclic graphs, which are simple undirected finite connected graphs of order

Carol T. Zamfirescu,

Communicated by Chunhui Lai:

Bu, Yuehua (Zbl 1212.05127).

Summary: A uniquely pancyclic digraph

11. Let

Using Math reviews, I found:

94i:05048 05C35

Lai, Chun Hui.

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),

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:

The authors prove

See also:

Chunhui Lai,

In this paper, it is proved that

From Lai Chunhui:

Let

and conjectured that

\ $\lim \frac{f

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]).

Further comments from Chunhui Lai, August 15, 2011:

Let

Further from Lai Chunhui:

Lai, Chunhui(PRC-ZNU-MIF); Liu, Mingjing(PRC-ZNU-MIF)

(MR3287706 Reviewed) 05C35

12. Prove: If

Erdös and Gallai proved that every such graph contains a path of length

Yair Caro: There are many partial results obtained in the last 10 years or so. The most notable are :

- The conjectured bound holds true if
*G*is*C*._{4}-free

J.F.Scale and M.Wozniak**JCT_B 70**(1997), 367-372 (extending an earlier result of Barndt and Dobson). - 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

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,

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,

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

14. The

The bandwidth of the

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

The question is even wide open for trees. Fan Chung (1988) proved that the gap is at least

U. Feige,

F.R.K. Chung,

Anupam Gupta,

15. A simple graph

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

L. Lovász has conjectured that

It is known that sqrt

Solved by: Stephanie Boyles and G. Exoo.

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

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

For example, every hamiltonian graph is 1-tough.

A

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:

H. Enomoto, B. Jackson and P.Katerinis.

The following interesting result was proven by Enomoto (1985):

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

A simple graph on

22(a). Prove that every graph

22(b). Prove that every graph

Woodall has shown that

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

R. Shi.

R. Shi.

R. Shi.

See also:

W. Goddard and D. J. Kleitman.

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

In general the conjecture is FALSE. There is a counter-example with

The

F.P. Ramsey.

24. Find the Ramsey number

It is known that

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

F.R.K. Chung,

A. Sanchez-Flores,

25. For

Folkman (1970) established the existence of such graphs.

Determine bounds for

It is known that

Klas Markstrom: The folkman number

Konrad Piwakowski, Stanislaw P. Radziszowski and Sebastian Urbanski,

Florida Atlantic University

777 Glades Road

Boca Raton, Florida 33431-0991

USA

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

Last modified December 30, 2013, by S.C. Locke.

(And updated only when somebody tells me something new to post.)