Unsolved Problems (Part 2)

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. I hope it will not annoy the authors of that text if I will reproduce that list here, and perhaps (eventually) add to it. Problems number above 50 are from other sources. 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.) Also, I'm not giving you all of the references in Bondy and Murty. You should get yourself a copy of that book.
26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

Problems 1-25, Problems 57-61.
26. Prove that every n-chromatic graph G has r(G,G) >= r(n,n) (P. Erdös, 1973).

Message from Stephan Brandt:
Disproved by Faudree and McKay [A Conjecture of Erdös and the Ramsey Number r(W6), J. Comb. Math. Comb. Comp. 13(1993), 23-31].
Counterexample: Wheel with 5 spokes has Ramsey number 17 < r(4,4).
27. What is the maximum possible chromatic number of a graph which can be drawn in the plane so that each edge is a straight line segment of unit length? (Moser, 1958)
Note: edges may cross here.
The answer is obviously one of 4, 5, 6 or 7.
28. Prove: The absolute values of the coefficients of any chromatic polynomial form a unimodal sequence (that is, no term is flanked by terms of greater value). (R.C. Read, 1968)
Caution: A similar conjecture about the coefficients of the Tutte polynomial is false.
29. Prove that if G is not complete and the chromatic number of G is m+n-1, where m>1 and n>1, then there exist disjoint subgraphs G1 and G2 of G with the chromatic number of G1 equal to m and the chromatic number of G2 equal to n (L. Lovász, 1972).

From: mas074@latech.edu
Subject: Regarding a problem in the unsolved Graph Theory problem list
To: lockes@fau.edu

Dear Dr. Locke,

This email is regarding correction of the statement of a problem (problem #29) in the Bondy-Murty book as posted in your website. The statement, as given in the book and also in your site is as follows:

"Prove that if G is not complete and the chromatic number of G is m+n-1, where m>1 and n>1, then there exist disjoint subgraphs G1 and G2 of G with the chromatic number of G1 equal to m and the chromatic number of G2 equal to n (L. Lovász, 1972)."

As our Graph Theory course project, we explored this problem and found that the statement is not true for a certain class of graphs containing complete subgraphs with (m+n-1) vertices. At that point, we were thinking that this was a new discovery. But later our professor found an alternative statement of the problem in the book named "GRAPH COLORING PROBLEMS" by Jensen and Toft. In page 104, section 5.12, the following problem is stated as the Erdos-Lovasz Tihany Problem:

"Let G be a k-chromatic graph containing no K_k (complete subgraph with k vertices) and let a and b be natural numbers with a,b >= 2 and a + b = k + 1. Does there exist a pair of disjoint subgraphs of G of chromatic numbers a and b, respectively?"

From this problem statement, it seems that it was previously known that there are counterexamples of the Lovasz Conjecture as stated in the Bondy-Murty book -- but these were not mentioned in the book. We just wanted to inform you about this in case you wanted to make adjustments to your web-site.

Regards,
Arafat

A simple graph G is perfect if, for every induced subgraph H of G, the number of vertices in a maximum clique (complete subgraph) of H is the chromatic number of H.

30. The strong perfect graph conjecture. Prove that G is perfect if and only if no induced subgraph of G or of GC, the complement of G, is an odd cycle of length greater than three (C. Berge, 1961).

Lovász (1972) has shown that the complement of a perfect graph is perfect.

See also: [K.R. Parthasarathy and G. Ravindra, c. 1976]

Solved, May 2002, by Maria Chudnovsky, Paul Seymour, Neil Robertson and Robin Thomas. See: http://www.cs.rutgers.edu/~chvatal/perfect/spgt.html#theorem. (Communicated to me by Lauri A. Hallila.)
31. Prove that if H is obtained by duplicating each edge of a 3-regular simple block (2-connected graph, in this case), then H has edge-chromatic number 6 (D.R. Fulkerson, 1971).

Warmup Exercise suggested by ZK (proof takes just a few sentences and quoting a well-known theorem):
Prove that H has edge-chromatic number at most 7.
32. Prove that if G is simple, with an even number of vertices, maximum degree D, and edge-chromatic number D+1, then for some vertex v, the graph G-v has the same edge-chromatic number as G has (I.T. Jakobsen, L.W. Beineke, R.J. Wilson, 1973).

This has been verified for all graphs with at most 10 vertices and for all cubic (3-regular) graphs on 12 vertices.

Thomas Niessen: A similar conjecture, called Critical Graph Conjecture, is formulated with respect to removing edges instead of vertices, and so far as I know that has been conjectured by Jakobsen, Beineke and Wilson (vertex-critical graphs with respect to egde-coloring are not so well investigated). It has been disproved by M.K.Goldberg, Construction of class 2 graphs with maximum vertex degree 3, JCT B 31(1981), 282-291. Nowadays lots of counterexamples are known. I have a new paper (St. Gruenewald and E. Steffen, Chromatic-index critical graphs of even order, DIMACS Technical Report 97-39(1997)), where the conjecture is cited with respect to removing edges. Moreover, this paper seems to be the best source for several counterexamples!
33. Prove: For any simple graph G with maximum degree D, the elements of V union E can be coloured in at most D+2 colours so that no two adjacent or incident elements receive the same colour. (M. Behzad, 1965)
This is known as the total colouring conjecture, and has been verified for D < 5. It is rather trivially true for bipartite graphs.

From Yair Caro:
Bruce Reed and Mike Molloy proved that the total coloring number of a graph G with maximum degree Delta is at most Delta+500. Here is a reference : A bound on the total chromatic number. (with Reed, Bruce) Combinatorica 18(1998) 241-280 05C15 (05C80)
34. Prove that every simple graph on n vertices, with more than 3n-6 edges, must contain a subdivision of K5 (G.A. Dirac, 1964).
Thomassen (1975) proved that every simple graph on n vertices, with at least 4n-10 edges, must contain a subdivision of K5.

Message from Stephan Brandt and augmented by Yair Caro:
Proven by W. Mader:
W. Mader, 3n-5 edges do force a subdivision of K5. Combinatorica 18(1998), pages 569-595.
35. A sequence d of non-negative integers is potentially planar if there is a simple planar graph with degree sequence d. Characterise the potentially planar sequences (S.L. Hakimi, 1963).
See also: [A.B. Owens, 1971]
36 and 37 (The Four-Colour Theorem). Proven by K. Haken and W. Appel, 1976.

36. Every loopless planar graph with n vertices contains an independent set of cardinality at least n/4. Conjectured by Erdös (1968).

37. Every planar graph is 4-colourable. Conjectured by F. Guthrie (1852).
38. Prove that every k-chromatic graph contains a subgraph contractible to Kk (Hadwiger, 1943).

G.A. Dirac (1964) proved every 6-chromatic graph contains a subgraph contractible to K6 less one edge.

Message from Stephan Brandt:
True for k<=6. The case k=6 was proven by Robertson, Seymour and Thomas [Hadwiger's conjecture for K6-free graphs, Combinatorica 13(1993), 279-362].
39. False: [Catlin noticed a couterexample: C3 crossproduct C5.]
Prove that every k-chromatic graph contains a subdivision of Kk (Hajos, 1961).
Pellikán (1969) showed that every 5-chromatic graph contains a subdivision of K5 less one edge.

Message from Siemion Fajtlowicz: Catlin found a counterexample to 39 in Hajos graph-coloring conjecture: variation and counterexamples, JCTB 26(1979) 268 -274. Erdos and Fajtlowicz proved that almost all graphs are counterexamples, and actually that in almost every graph, the subdivision number is approximately square root of k, where k is the chromatic number. Combinatorica 4(1981), Number 1, 35 - 38.
40. Prove that every 2-edge-connected 3-regular simple graph which has no Tait colouring (3-edge-colouring) contains a subgraph contractible to the Petersen graph (W.T.Tutte, 1966).
See lots of pretty examples in the paper:
R. Isaacs. Infinite families of nontrivial trivalent graphs which are not Tait colourable. American Mathematical Monthly 82(1975), 221-39.
M. Gardner. Mathematical Games column, Scientific American 234, number 4(April 1976),126-130

Communicated to me by Christopher Heckman, checkman@math.gatech.edu: #40 (Tutte's 3-edge coloring conjecture) is true; it was proven by Robertson, Sanders, Seymour, and Thomas, announced at the DIMACS DREI conference in Rutgers August 1998. They also found a simplified proof of the 4-Color Theorem ("Unsolved Problem" #37 and #36 as a corollary) which was published earlier this year.
41. Prove that, for every surface S, there exists a finite number of graphs which have minimum degree at least three and are minimally non-embeddable on S.
Strong warning: See the large collection of papers by Seymour and Robertson in the Journal of Combinatorial Theory, Series B.
A directed graph D is diconnected if for any ordered pair of vertices (u,v), there is a directed path from u to v.

42. If D is diconnected, with chromatic number k, then D has a directed cycle of length at least k.
Conjectured by M. Las Vergnas (1974).
Solved by J.A. Bondy (1976).
A tournament is a loopless directed graph D with exactly one arc between each pair of distinct vertices. A balanced tournament is a tournament with indegree equal to outdegree at every vertex. A balanced tournament must obviously have an odd number of vertices.

43. Let D be a balanced tournament with n vertices. Prove that D is the union of (n-1)/2 arc-disjoint directed Hamilton cycles (P. Kelly, 1966).
Let D be a directed graph. For each vertex v of D, define excess(v) by excess(v)=max{0,outdegree(v)-indegree(v)}. Now define excess(D) by excess(D)=excess(v1)+...+excess(vn), where V(D)={v1,...,vn}.

44. Prove that any tournament D on an even number of vertices is the union of excess(D) arc-disjoint directed paths (R. O'Brien, 1974).

This would imply the truth of conjecture 43.
45. Characterise the tournaments D with the property that all subtournaments D-v are isomorphic (A. Kotzig, 1973).
46. Prove that every direcetd graph D which contains a directed cycle must have an arc whose reversal decreases the number of directed cycles in D (A. Adám, 1963).

Contributed by Wouter van Doorn: In the 42nd Volume of the Journal of Combinatorial Theory, Series B, Carsten Thomassen gave infinitely many counterexamples to Adam's conjecture on arc reversals in his paper "Counterexamples to Adam's conjecture on arc reversals in directed graphs".

Thomassen, Carsten, Counterexamples to Adám's conjecture on arc reversals in directed graphs. J. Combin. Theory Ser. B 42(1987), 128–130.

A few years later, Jirásek noted that examples of Locke and Morris (né Witte), of non-hamiltonian graphs also produce counterexamples to Adam's conjecture.

Jirásek, Jozef, Arc reversal in nonhamiltonian circulant oriented graphs. J. Graph Theory 49(2005), 59–68.

S.C. Locke and D. Witte. On non-hamiltonian circulant digraphs of outdegree three. Journal of Graph Theory 30(1999), 319-331.
47. Prove: Given a positive integer n, there exists a least integer f(n) such that in any directed graph with at most n arc-disjoint cycles there are f(n) arcs whose deletion destroys all directed cycles (T. Gallai, 1964; D.H. Younger, 1968).

See also: [P. Erdös and L. Pósa, 1962] [Younger, 1973]

Also: I think this one has been recently solved.
An (m+n)-regular graph is (m,n)-orientable if it can be oriented so that each indegree is either m or n.

48. Prove that every 5-regular simple graph with no 1-edge-cut or 3-edge-cut is (4,1)-orientable (W.T. Tutte, 1972).

Tutte has shown that this would imply Grötzsch's theorem.
49. Obtain an algorithm to find a maximum flow in a network with two sources x1 and x2, two sinks y1 and y2, and two commodities, the requirement being to ship commodity 1 from x1 to y1 and commodity 2 from x2 to y2 (L.R. Ford and D.R. Fulkerson, 1962).

See also: [B. Rothschild and A. Whinston, 1966]
50. The 5-flow conjecture.

Prove: Every 2-edge-connected digraph D has a circulation f over the field of integers modulo 5 in which f(e) is nonzero for every arc e. (W.T. Tutte, 1949)

Tutte has shown that this would imply the five-colour theorem.
F. Jaeger proved: Every 2-edge-connected digraph D has a circulation f over the ring of integers modulo 8 in which f(e) is nonzero for every arc e.
P. Seymour proved: Every 2-edge-connected digraph D has a circulation f over the ring of integers modulo 6 in which f(e) is nonzero for every arc e.
The cycle double cover conjecture. (Compare to conjecture 31.)

A cycle double cover of a graph G is a collection C of cycles of G such that every edge of G occurs in exactly two members of C. The collection is orientable if each cycle in the collection can be given an orientation such that for every edge e the orientations of e in the two members of C are opposite. The collection is k-colourable if the members of C can be assigned colours from {1,2,...,k} such that for every edge e the colours of the two members of C containing e are distinct.

By Haken and Appel, every 2-edge-connected planar graph has a 4-colourable orientable cycle double cover.

Similarly, If G can be embedded on an orientable surface S such that every face boundary is a cycle, then G has an orientable cycle double cover.

Tarsi (1986) and L. Goddyn (1989) proved that every 2-edge-connected graph with a Hamilton path has a 6-colourable cycle double cover.

Early references to the cycle double conjecture include: [P. Seymour, 1979] [G. Szekeres, 1973]

For an excellent survey article see:
F. Jaeger. A survey of the cycle double conjecture. Cycles in Graphs, Annals of Discrete Mathematics 27(1985), 1-12.

Conjecture 51. Prove that every 2-edge-connected graph has an orientable 5-colourable cycle double cover.

This would imply conjecture 50.
52. A variant of the Dinitz Conjecture.

Let n be a given integer, and let Sij be sets of integers, with |Sij|=n, for i,j in {1,2,...n}. The Dinitz Conjecture asked whether one could always choose elements aij from Sij such that the matrix (aij) is Latin (has no repeated elements in any column or in any row). This was solved by Fred Galvin (JCTB? - I need to look up the reference).

For the rest of this problem: the sets Sij are "given", and we ask about Dinitz squares on this choice of sets.

While Charles Colbourn, Ryoh Fujihara and I were having lunch (March 7, 1997), Ryoh asked if there might be a pair L1, L2 of orthogonal Dinitz squares, and what conditions might need to be added. [Obviously one has a problem if n=6 and if every Sij={1,2,3,4,5,6}.] Charlie asked what happens if instead of orthogonal, we require disjoint. An even weaker question he asked: is there always more than one Dinitz square (can you find L1 and L2 which are not equal)? There are exponentially many Latin squares of side n, are there exponentially many Dinitz squares?

L1 and L2 are othogonal if the ordered pairs of corresponding elements are all distinct. L1 and L2 are disjoint if corresponding entries are distinct.
53. For each k>3, find a connected circulant non-hamiltonian directed graph with outdegree k.

Locke and Witte show an infinite family for k=3.
54. A graph G is k-path-connected if for any two distinct vertices u and v of G there is a (u,v)-path of length at least k. A graph G is k-generated if the cycle space has a basis consisting of cycles of length at least k. Under some conditions, a graph must be both (k-1)-path-connected and k-generated (see, for example, Alspach, Locke and Witte (1990), Locke (DM 1985), Locke (EJC 1985), Hartman (M.S. Thesis, Waterloo, 1982)(EJC 1983), Bondy and Lovasz (Combinatorica, 1981).

If a 2-connected graph is (2k-1)-generated, it is obviously k-path-connected. The connection the other way was not so obvious to me at that time. What appears in the 1992 paper is that if G is ((k-1)2+1)-path-connected, then G is (k+1)-generated. See Locke (1992). Warning, Conjecture 4 of that paper is false (take subdivisions of the dodecahedron). But Conjecture 5 of that paper is correct:

Question 54. What is the best positive constant m such that every k-path-connected graph must be (mk)-generated.

It is obvious that any k-path-connected graph G (other than K1) must have a cycle of length at least k+1 in each block. Thus, G is t-generated for k+3<=2t<=k+4. (HTML doesn't yet have a nice way of saying: t is the least integer bounding half of k+3 from above.)

(H.J. Voss visited me in 2002, after the 33rd CGTC Conference and, having forgotten I had already posted the above note (c. 2000), we generated the proof again.)

Thus, the best value for m, such that every k-path-connected graph must be (mk)-generated, is somewhere between 1/2 and 17/18. In the 1992 paper, I also determined some specific values of f(k), where f(k) is the largest integer w such that every k-path-connected graph must be w-generated. In particular, f(k)=k, for k=3,4,5. My current Ph.D. student will determine a few more values of f(k) and/or improve the bounds slightly -- the proof that f(6)=6 is nearly complete.
55. Let ck, k>2, denote the best possible constant such that every k-connected graph containing a path of length p must also contain a cycle of length at least ckp. Bondy and Locke (1981) showed that c3 is between 2/5 and 1/2.

Question 55. Does the sequence c3,c4,... approach 1?

Question 55(b). Let dk denote a similar parameter for k-regular, k-connected graphs. Thus, d3 is between 2/3 and 7/8. Is the sequence d3,d4,... non-decreasing and does it approach 1?

A picture of a 2-connected graph.
56. Albertson-Bollobas-Tucker conjecture. Heckman-Thomas solution

In 1976, Albertson, Bollabas, and Tucker conjectured that every n-vertex triangle-free planar cubic graph has an independent set of cardinality at least 3n/8. This conjecture was proven by Heckman and Thomas.

Fraughnaugh and Locke proved that every n-vertex triangle-free connected cubic graph has an independent set of cardinality at least (11n-4)/30.

References.

K. Fraughnaugh and S.C. Locke. 11/30 (finding large independent sets in connected triangle-free 3-regular graphs. Journal of Combinatorial Theory, Series B 65(1995), 51-72.

C. C. Heckman, R. Thomas, Independent Sets In Triangle-Free Cubic Planar Graphs, Journal of Combinatorial Theory, Series B, 96(2006), 253-275. (pdf version).
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/unsolv2.htm

Last modified July 21, 2006, by S.C. Locke.