BRICS LS-01-1 Z. Tuza: Unsolved Combinatorial Problems, Part I BRICS

Basic Research in Computer Science

Unsolved Combinatorial Problems Part I

Zsolt Tuza BRICS Lecture Series LS-01-1 ISSN 1395-2048 May 2001 Copyright \begin{matrix}c \\ ◯ \end{matrix} 2001, Zsolt Tuza.

BRICS, Department of Computer Science University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Lecture Series publications. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk
ftp://ftp.brics.dk

This document in subdirectory LS/01/1/

Unsolved Combinatorial Problems Part I

Zsolt Tuza

Zsolt Tuza

tuza@sztaki.hu

Computer and Automation Research Institute Hungarian Academy of Sciences H–1111 Budapest, Kende u. 13–17

and

Department of Computer Science

University of Veszprém H–8200 Veszprém, Egyetem u. 10

Hungary

Latest update on 2001–5–28

Preface

Many young researchers, and also those students who feel attracted towards research, have encountered the difficulty that the “ famous ” open problems are too well-known, much studied, and hence almost hopeless to attack, while lots of others are rather technical and, therefore, maybe less exciting to begin with. From this starting point, several colleagues encouraged me at different times and places to write up a list of research problems which are easy to state and still less known. A good opportunity and further positive motivation occurred to me when I got invited to BRICS to deliver a PhD mini-course under the title “ Challenges in Combinatorics.”

The course took place in Århus in October/November 2000. Beside the open questions presented there, which served a basis for the first manuscript, the current version of this collection contains many further research problems, too. The references included here are far from being complete, nevertheless they are sufficient to start with ; pointers to further reading can also be found in them.

During the course, various related results and proof techniques were also discussed, but they are not included in these notes.

It is our hope that this modest effort will reach its goal and some of the problems mentioned here will get solved. As a matter of fact, I am pleased to say that in one of the questions related to Section 7 substantial development was achieved already during the course, resulting in a forthcoming publication.

The order in the arrangement of the material is not strictly systematic ; to facilitate finding specific types of questions, interrelated subjects are organized around some key words listed at the end. Moreover, also the most frequently used notation is collected there.

These preliminary words would not be complete without expressing my thanks to my co-authors whom it has been a great pleasure to work with on these subjects — they are too many to list them by name here — and also to Riko Jacob, Peter Bro Miltersen, and Anders Yeo at BRICS, for their active participation at the course and useful comments of various depths in connection with some of the problems. I would also like to say many thanks to Erik Meineche Schmidt for his encouragement as a major step before the birth of this problem collection. Last but not least, the inspirative working atmosphere and warm hospitality at BRICS is gratefully acknowledged. vi

Contents

Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v

1. Subset-Sums Equality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2. Boolean Satisfiability and Hypergraph 2-Coloring with

bounded degrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 3. Second Hamiltonian Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4. The number of Hamiltonian subgraphs . . . . . . . . . . . . . . . . . . . . . . . 6 5. Local vs. global average degree in graphs . . . . . . . . . . . . . . . . . . . . . 8 6. Uniform edge cover with triangles . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 7. Single Input Double Output controllers . . . . . . . . . . . . . . . . . . . . . . 11 8. Ryser’s conjecture on r-partite hypergraphs . . . . . . . . . . . . . . . . . . 12 9. Covering the triangles with edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 10. Largest bipartite subgraphs of graphs . . . . . . . . . . . . . . . . . . . . . . . . 15 11. Weighted edge covering with complete subgraphs . . . . . . . . . . . . 17 12. Strongly triangle-free subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 13. Excluded cycle lengths, chromatic number, and orientations . 21 14. The Acyclic Orientation Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 15. Transversals of uniform hypergraphs . . . . . . . . . . . . . . . . . . . . . . . . . 24 16. Covering and coloring the maximal complete subgraphs . . . . . . 25

Basic notation and terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Key words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 viii

1. Subset-Sums Equality

1. Subset-Sums Equality

There are many interesting problems where the existence of a solution is guaranteed by some theoretical reason, while it is not known whether the corresponding search problem is polynomial-time solvable. One of the simplest-looking examples is the following one, whose solution is easily derived via the pigeon-hole principle.

Problem 1 Let a_{1}, …, a_{n} be natural numbers such that

a_{1} + … + a_{n} < 2^{n} − 1 .

Then there exist two distinct subsets A, A′ ⊂ {1, …, n} such that

∑_{i∈A} a_{i} = ∑_{i∈A′} a_{i} .

Can one find such A, A′ in polynomial time ?

It is worth noting that, in the opinion of some respected cryptographers, the problem is hard, even on the average. Based on this strong assumption of hardness, a cryptographic scheme (more precisely, a scheme for collision-intractable — or, in another terminology, universal one-way — hashing) has been suggested. It seems that even this scheme has not yet been broken.

On the other hand, denoting s(A) = ∑_{i∈A} a_{i}, it is known that the ratio

min_{{A,A′⊂\{1,...,n\} \atop A∩A′=∅}} max \{\frac{s(A)}{s(A′)}, \frac{s(A′)}{s(A)}\}

can be approximated by a FPTAS.

[1] C. Bazgan – M. Santha – Zs. Tuza : Efficient approximation algorithms for the Subset-Sums Equality problem. Proc. ICALP ’98 (K. G. Larsen et al., eds.), Lecture Notes in Computer Sci. 1443, Springer-Verlag (1998), 387–396.

[2] R. Impagliazzo – M. Naor : Efficient cryptographic schemes provably as secure as subset sum. J. Cryptology 9 (1996), 199–216.

Preliminary version in : Proc. 30th FOCS (1989).

[3] N. Megiddo – C. Papadimitriou : On total functions, existence theorems and computational complexity. Theor. Computer Sci. 81 (1991), 317–324.

[4] C. Papadimitriou : On the complexity of the parity argument and other inefficient proofs of existence. J. Computer and System Sci. 48 (1994), 498–532.

2. Satisfiability and coloring with bounded degrees

2. Boolean Satisfiability and Hypergraph 2-Col-oring with bounded degrees

One aim of the problems in this section is to draw a shaper line between polynomial-time solvability and NP-completeness. We consider restricted versions of the Satisfiability problem. For natural numbers k, s let us call a Boolean formula in conjunctive normal form a (k, s)-formula if each of its clauses contains precisely k literals and each variable occurs in at most s clauses. Then (k, s)-SAT is defined as Satisfiability restricted to (k, s)-formulas.

For each k ≥ 3, denote by d = d(k) the largest s such that every (k, s)-formula is satisfiable. It can be proved that the complexity of SAT jumps very suddenly, namely that already (k, d+1)-SAT is NP-complete.

Problem 2 Determine the exact value of d(k), or its asymptotic behavior as k gets large.

The condition k ≥ 3 is necessary to assume, because 2-SAT is well-known to be solvable in linear time. For exact values, d(3) = 3 and d(4) = 4 was proved by Tovey and by Jitka Stříbrná (one of Kratochvíl’s students), respectively. As regards asymptotics, it is known that

c \frac{2^{k}}{k} ≤ d(k) ≤ c′ 2^{k}

for some positive constants c, c′. Hence, the next problem is to decide whether or not the function

k − log_{2} d(k)

tends to infinity as k → ∞, and similarly for

log_{2} d(k) − k + log_{2} k .

From the algorithmic point of view, a natural question is :

Problem 3 Assuming s ≤ d(k), how hard is it to find a satisfying truth assignment of a (k, s)-formula ?

A (k, k)-formula can be satisfied via Hall’s theorem in polynomial time, hence settling the cases of k = 3, 4. It would be of some interest to know — and perhaps not very hard to determine — the limits of this approach :

Problem 4 Find the largest k such that d(k) = k.

It follows from the known lower bounds on d(k) that this value is smaller than 8.

For larger k, a more involved algorithmic version of the Lovász Local Lemma can be applied to a considerably large range of s, up to 2^{ck} for some small constant c > 0. As it can be seen, however, there is a large gap between this interval and the currently best known lower bounds on d(k).

The analogous problem turns out to be quite delicate for Hypergraph 2-Colorability. The latter is intimately related to Not-All-Equal Satisfiability (though not so much to SAT). Denoting by d′(k) the largest integer s such that every k-uniform hypergraph (k ≥ 3) is 2-colorable, it can be proved that Hypergraph 2-Colorability restricted to k-uniform hypergraphs of maximum degree d′(k) + 2 is already NP-complete. It is a challenging problem to analyze the situation for maximum degree d′(k) + 1.

Problem 5 Is the 2-colorability of k-uniform hypergraphs with maximum degree d′(k) + 1 decidable in polynomial time ?

The answer is affirmative for k = 3 (then d′(3) = 2), but we do not know what happens when k is larger.

[5] J. Beck : An algorithmic approach to the Lovász Local Lemma. Random Structures and Algorithms 2 (1991), 343–365.

[6] O. Dubois : On the r, s–SAT satisfiability problem and a conjecture of Tovey. Discrete Applied Math. 26 (1990), 51–60.

[7] P. Erdős – L. Lovász : Problems and results on 3-chromatic hypergraphs and some related questions. Infinite and Finite Sets (A. Hajnal et al., eds.), Colloq. Math. Soc. J. Bolyai 10, North-Holland (1974), 609–627.

[8] J. Kratochvíl – P. Savicky – Zs. Tuza : One more occurrence of variables makes satisfiability jump from trivial to NP -complete. SIAM J. on Computing 22 (1993), 203–210.

[9] J. Kratochvíl – Zs. Tuza : Double degree jump for hypergraph 2coloring. Manuscript, 2001.

[10] J. Stříbrná : Diploma thesis, Charles University, 1994.

[11] C. A. Tovey : A simplified satisfiability problem. Discrete Applied Math. 8 (1984), 85–89.

3. Second Hamiltonian Cycle

3. Second Hamiltonian Cycle

The next problems exhibit some algorithmic aspects related to Smith’s theorem. C. A. B. Smith proved (see the paper by Tutte) that each edge of a cubic (i.e., 3-regular) graph is contained in an even number of Hamiltonian cycles. This implies, in particular, that if a cubic graph is Hamiltonian, then it has more than one Hamiltonian cycle.

Problem 6 Let G be a cubic graph, and H ⊂ G a given Hamiltonian cycle in it. Can one find another Hamiltonian cycle H′ ⊂ G, H′ ≠ H, in polynomial time ?

The polynomial-time solvability of this problem is equivalent to the existence of a FPTAS for approximating in length — as a search problem — the second longest cycle in cubic Hamiltonian graphs, provided that one longest cycle is given in the input. (Run the FPTAS with approximation ratio 1 − \frac{1}{n+1}, for instance.) It is known that under these conditions an EPTAS exists. Without having one Hamiltonian cycle at hand, however, cycles of length Ω(n) are NP-hard to find, i.e., the longest cycle is not constant approximable, even in the restricted class of cubic Hamiltonian graphs. This leads to the folowing questions.

Problem 7 Assuming that the cubic graph G is Hamiltonian, but its Hamiltonian cycle H is not given in the input, how long cycles can be found in polynomial time ?

More generally, one can ask :

Problem 8 Investigate the analogous problem without assuming that the graph is 3-regular.

In the latter two problems, any length sequence growing faster than Θ(log n) would be of interest.

In a more general setting, Thomason’s method for finding a second Hamiltonian cycle works in every regular graph of odd degree. For regular graphs of even degrees, Sheehan formulated an analogous conjecture more than 25 years ago.

Problem 9 Prove that every 4-regular Hamiltonian graph contains a second Hamiltonian cycle.

An affirmative answer would imply the existence of a second Hamiltonian cycle (provided that the first one is guaranteed to exist) for every regular graph of even degree. That a second cycle exists indeed, has been proved for sufficiently large even degrees. The current record seems to be d ≥ 74.

[12] N. Alon – R. Yuster – U. Zwick : Color-coding : a new method for finding simple paths, cycles and other small subgraphs within large graphs. Proc. 26th STOC (1994), 326–335.

[13] C. Bazgan – M. Santha – Zs. Tuza : On the approximation of finding a(nother) Hamiltonian cycle in cubic Hamiltonian graphs. J. Algorithms 31 (1999), 249–268.

Preliminary version in : Proc. STACS ’98, Lecture Notes in Computer Sci. 1373, Springer-Verlag (1998), 276–286.

[14] K. Cameron : Krawczyk’s graphs show Thomason’s algorithm for finding a second Hamilton cycle through a given edge in a cubic graph is exponential. Proc. 5th Czech–Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague, July 1998.

[15] P. Horák – L. Stacho : A lower bound on the number of Hamiltonian cycles. Discrete Math. 222 (2000), 275–280.

[16] D. Karger – R. Motwani – G. D. S. Ramkumar : On approximating the longest path in a graph. Algoritmica 18 (1997), 82–98.

[17] J. Sheehan : The multiplicity of Hamiltonian circuits in a graph. Recent advances in graph theory, Proc. 2nd Czechoslovak Symposium, Prague, 1974, Academia Praha (1975), 477–480.

[18] A. G. Thomason : Hamiltonian cycles and uniquely edge colourable graphs. Advances in graph theory, Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977, Annals of Discrete Math. 3 (1978), Exp. No. 13, 3 pp. ; MR 80e:05077

[19] C. Thomassen : Independent dominating sets and a second Hamiltonian cycle in regular graphs. J. Combinatorial Theory B 72 (1998), 104–109.

[20] W. T. Tutte : On Hamiltonian circuits. J. London Math. Soc. 21 (1946), 98–101.

4. The number of Hamiltonian subgraphs

4. The number of Hamiltonian subgraphs

In a graph G = (V, E), let us call a vertex set X ⊆ V a Hamiltonian subset if the subgraph of G induced by X has a Hamiltonian cycle. The following problem was raised by Komlós (Private communication, 1981).

Problem 10 Prove that among all graphs of minimum degree d, the complete graph K_{d+1} has the smallest number of Hamiltonian subsets.

Analogously, we can ask :

Problem 11 Determine the minimum number of Hamiltonian subsets in bipartite graphs of minimum degree d.

We expect that the minimum occurs for the complete bipartite graph K_{d,d}.

Problem 12 Study the above questions for graphs of average degree d.

Concerning extremum, perhaps the following — slightly weaker — assertions will be easier to prove (if they are true at all). We formulate them in this way partly because the numbers appearing there look nicer than those in the original versions of the problems.

1. The number of Hamiltonian subsets together with ∅, with the vertices and the edges, is at least 2^{d+1} in every graph of minimum (or, average) degree d.

2. The number of Hamiltonian subsets together with ∅ and the edges, is at least \binom{2d}{d} in every bipartite graph of minimum (or, average) degree d.

If these bounds are valid, their tightness would again be demonstrated by K_{d+1} and K_{d,d}, respectively. As a more modest goal, one can ask :

Problem 13 Find lower bounds of the type Ω(c^{d}) for some constant c > \sqrt{2}.

There are many ways to raise similar questions concerning lower bounds on the number of Hamiltonian subgraphs, in terms of further interesting graph invariants such as e.g. connectivity, diameter, generalized neighborhood conditions (i.e., where the unions and/or intersections of neighborhoods of a given number of vertices are required to have a prescribed cardinality), etc.

Perhaps some very interesting general results can be found in the following direction :

Let F be any fixed graph. A subdivision S(F) of F is obtained when we replace some of the edges by internally disjoint paths such that their internal vertices are also distinct from the vertices of F. Moreover, let us say that two subgraphs of a graph G are distinguishable if their vertex sets are different.

Problem 14 For which graphs F do there exist constants c = c(F) > 1 and c′ = c′(F) > 0 such that the following assertion is valid for every integer t sufficiently large with respect to F :

If each edge of a graph G is contained in at least t subgraphs isomorphic to F, then G contains at least c^{t^{c′}} distinguishable subdivisions of F.

Since the cycles are just the subdivisions of the triangle K_{3}, the known results imply an affirmative answer with c ≥ \sqrt{2} and c′ = 1 for F = K_{3}. On the other hand, the exact value of the best possible c is not known even for this — seemingly simplest — particular case. In general, the best value one can expect for c′ is \frac{1}{|V (F)|−2} , and perhaps it will not be hard to analyze whether this is attained for F. It is not clear, however, for which graphs F it will be easy to determine the largest possible c(F).

Instead of minimum, one may also be interested in the maximum number of Hamiltonian subgraphs as well. Since in a complete graph every induced subgraph with more than two vertices is Hamiltonian, to avoid trivialities we should be more restrictive. Here is the simplest case to start with :

Problem 15 At most how many induced cycles can a graph with n vertices have ?

Note that no two induced cycles can have the same vertex set, i.e. they surely are distinguishable.

If n is a multiple of 3, in order to obtain a lower bound we can start with a cycle of length n/3, substitute a 3-element independent set for each of its vertices, and replace each edge with a complete bipartite graph K_{3,3}. Then the number of induced cycles of length n/3 is as large as 3^{n/3} (and further 3n induced 4-cycles occur between the consecutive triples of vertices). We do not know whether this is the maximum one can get. Observe that if n ≡ 3 (mod 6), then we obtain 3^{n/3} cycles of odd lengths. So, perhaps the next problem — motivated by the study of highly imperfect graphs — is easier to solve than the previous one.

5. Local vs. global average degree in graphs

Problem 16 Determine the largest possible number of induced odd cycles in a graph with n vertices.

Chvátal and myself guessed (in 1988) that the right answer is 3^{n/3}. It can be proved that 2^{cn} is an upper bound, with some absolute constant c < 1.

[21] Zs. Tuza : Exponentially many distinguishable cycles in graphs. J. Combinatorics, Inf. Syst. Sci. 15 (1990), 281–285.

[22] : Problems and results on graph and hypergraph colorings. Le Matematiche 45 (1990), 219-238.

5. Local vs. global average degree in graphs

It may be sort of surprising that the average degree in the neighborhood of each vertex of a graph on n vertices may as well be about \sqrt{n} times larger than the average degree of the graph in question. In order to formulate the problem, let us denote by

\overline{d} = \frac{∑_{i=1}^{n} d_{i}}{n}

the average dgree of G, and for each 1 ≤ i ≤ n by

d̃_{i} = \frac{∑_{v_{i}v_{j}∈E} d_{j}}{d_{i}}

the average degree in the (open) neighborhood of v_{i}.

Problem 17 Determine the largest possible value of

min_{1≤i≤n} \frac{d̃_{i}}{\overline{d}} ,

as a function of n, taken over all bipartite graphs on n vertices.

In particular, prove or disprove that the maximum is obtained — at least asymptotically — by the following construction. Start with a complete bipartite graph K_{p,p} as the “ center ” of G, where p ∼ c\sqrt{n} for some constant c to be fixed later. Split the other n − 2p vertices into 2p mutually disjoint sets of sizes as equal as possible. Join the vertices of the i^{th} set with the i^{th} vertex of the central K_{p,p}. In this graph, 2p = Θ(\sqrt{n}) vertices have degree Θ(\sqrt{n}) and n − 2p vertices are of degree 1, hence the average degree is bounded above by a constant whenever c is fixed. On the other hand, in the neighborhood of a central vertex, the local average degree is linear in n. Fixing now c optimally, we obtain that the largest possible ratio is at least \frac{1}{4} \sqrt{n} − 1. Perhaps this lower bound is tight, apart from an additive constant.

In trees the extremum of the above ratio is almost completely determined, but still there is an additive constant gap between the general lower and upper bounds of \frac{1}{2} ^{3} \sqrt{n} − \frac{1}{2} and \frac{1}{2} ^{3} \sqrt{n} + \frac{1}{3}. Maybe the extremal constructions will be relatively easy to characterize.

It is also of interest to study vertices v_{i} satisfying d̃_{i} ≥ \overline{d}. Such vertices are called groupies. While it is fairly simple to show that every graph contains at least one groupie, it needs some neat computation that there always exist at least two of them (except for K_{1}). One can ask what happens in a “ typical ” graph :

Problem 18 Determine the number of groupies in the random graph G_{n,p}.

Though this number is known to be linear in n for every fixed p > 0, the exact asymptotics is unknown, even for the seemingly simplest particular case of p = 1/2.

[23] E. Bertram – P. Erdős – P. Horák – J. Širáň – Zs. Tuza : Local and global average degree in graphs and multigraphs. J. Graph Theory 18 (1994), 647–661.

[24] W. Fernandez de la Vega – Zs. Tuza : Groupies in random graphs. (to appear)

[25] J. Mackey : A lower bound for groupies in graphs. J. Graph Theory 21 (1996), 323–326.

[26] S. Poljak – T. Szabó – Zs. Tuza : Extremum and convergence of local average degrees in graphs. Congressus Numerantium 112 (1995), 191–198.

6. Uniform edge covering with triangles

6. Uniform edge covering with triangles

Solutions to the following problems would be of great interest in the theory of Steiner Triple Systems, especially on those of higher index.

In a graph G = (V, E), let us call a triple {e, e′, e′′} ⊆ E of edges a triangle if they are induced by a 3-element vertex set, i.e. if they are the edges of some K_{3} ⊆ G. Denote by T the set of all triangles in G. A uniform cover of the edges with triangles is a real-valued function

f: T → [0, 1]

such that

∑_{{T ∈T \atop e∈T}} f(T) = 1

for each edge e ∈ E.

Problem 19 Give a structural characterization of the graphs admitting a uniform cover.

This problem is interesting in itself as well ; but in the context of Steiner Triple Systems, the following question is even more relevant.

Problem 20 Characterize the graphs G admitting a uniform cover with weights strictly smaller than 1, such that the complement of G has a partition into mutually edge-disjoint triangles. Moreover, within this class, which are those graphs where in every uniform cover, all weights are < 1 ?

In between Problems 19 and 20, we can also ask :

Problem 21 What kind of structural properties ensure that both the graph and its complement admit uniform covers ?

More generally, motivated by the study of BIBDs of larger block size, the following problems arise :

Problem 22 Let q > 3 be any integer. Investigate the analogous problem for uniform edge covers of G with complete subgraphs K_{q} ⊆ G.

Problem 23 For q > p ≥ 2, study the existence of uniform edge covers of the complete subgraphs K_{p} ⊂ G with the K_{q} ⊆ G.

7. Single Input Double Output controllers

Certainly, also these two problems can be studied under the assumption that the properties in question hold simultaneously in G and in its complement.

[27] C. J. Colbourn – E. S. Mahmoodian : The spectrum of support sizes for threefold triple systems. Discrete Math. 83 (1990), 9–19.

[28] S. Milici – Zs. Tuza : The spectrum of λ-times repeated blocks for T S(v, λ). Discrete Math. 129 (1994), 159–166.

[29] : Coverable graphs. Studia Sci. Math. Hungar. 30 (1995), 329–344.

[30] A. Rosa – D. Hoffman : The number of repeated blocks in twofold triple systems. J. Combinatorial Theory A 41 (1986), 61–88.

7. Single Input Double Output controllers

The following types of problems have arisen in connection with the structural controllability of dynamic systems.

Let G = (V, E) be a graph with a given vertex partition X ∪ Y = V, such that X is an independent set and |Y | = 2 |X|. Our goal is to split G into vertex-disjoint copies of P_{3}, if possible, in such a way that each part has precisely one vertex in X. (The P_{3} need not be induced subgraphs, i.e. they are allowed to induce triangles.)

Problem 24 What kind of structural assumptions on G ensure that the decision of whether such a partition exists — and the search of a feasible partition if it exists — can be done in polynomial time ?

Problem 25 Investigate the analogous problem for directed graphs, where all edges incident to X are oriented from X to Y , and each P_{3} of the partition either has its middle vertex in X (and hence is alternately oriented) or has its starting vertex in X and is oriented consecutively.

One necessary condition, termed the Neighborhood-Matching Condition, can be obtained as follows. For any Z ⊆ X, consider the set N(Z) of vertices adjacent to Z (since X is supposed to be independent, N(Z) ⊆ Y holds). Let n(Z) = |N(Z)|, and denote by m(Z) the largest number of mutually vertex-disjoint edges from N(Z) to Y \ N(Z). It is easy to see that if a feasible partition exists, then

n(Z) + m(Z) ≥ 2 |Z|

8. Ryser’s conjecture on r-partite hypergraphs

holds for all Z ⊆ X. It is far from being obvious, but still true, that this condition can be tested in polynomial time.

Problem 26 Characterize those graphs for which the above condition is not only necessary but also sufficient for the existence of a feasible partition.

[31] K. M. Hangos – Zs. Tuza : Process structure driven control structure selection. IFAC World Congress (1996), Vol. M, 187–192.

[32] : Computational aspects of graph theoretic methods in control. Computer Intensive Methods in Control and Signal Processing — Can We Beat the Curse of Dimensionality? (L. Berec et al., eds.), 2nd European IEEE Workshop, Prague, Czech Republic (1996), 25–36.

[33] : Optimal control structure selection for process systems. Computers and Chemical Engng. (to appear)

[34] K. M. Hangos – Zs. Tuza – A. Yeo : Some complexity problems on Single Input Double Output controllers. BRICS Report Series RS-01-18, May 2001. (to appear)

8. Ryser’s conjecture on r-partite hypergraphs

The following general inequality bounding the transversal number above by a function of the matching number — proposed by Ryser in the mid-1970s — would be a nice generalization of Kőnig’s theorem on bipartite graphs. For any natural number r ≥ 3, call a hypergraph r-partite if its vertex set is partitioned into r mutually disjoint subsets in such a way that each edge of the hypergraph has precisely one vertex in each part.

Problem 27 Prove that every r-partite hypergraph H satisfies the inequality

τ(H) ≤ (r − 1) ν(H) .

Even the following particular case is open, apart from some small values of r:

Problem 28 In particular, assuming H ∩ H′ ≠ ∅ for all H, H′ ∈ H, prove

τ(H) ≤ r − 1 .

9. Covering the triangles with edges

Perhaps an answer to the following rather restricted question will already need some significant new ideas.

Problem 29 As a small unsolved case, determine

max_{H} τ(H)

where the maximum is taken over all intersecting, 7-partite hypergraphs. Is it equal to 5, 6, or 7 ?

Ryser’s conjecture is proved so far only for r = 3 (for ν unrestricted), via a beautiful generalization of the Kőnig–Hall theorem ; and for r = 4, ν ≤ 2, and r = 5, ν = 1, “ by hand.”

[35] R. Aharoni : Ryser’s conjecture for tripartite 3-graphs. Combinatorica 21 (2001), 1–4.

[36] Zs. Tuza : Some special cases of Ryser’s conjecture. MTA SZTAKI Working Paper, 1979.

[37] : Ryser’s conjecture on transversals of r-partite hypergraphs. Ars Combinatoria 16B (1983), 201–209.

9. Covering the triangles with edges

Though the following conjecture has the same quantitative form as Ryser’s one for r = 3, there is no evidence so far that they are related structurally as well. For a given graph G = (V, E), we consider its “ triangle hypergraph,” whose vertex set is E, and a triple of its vertices is an edge if and only if the corresponding three edges of G form a triangle.

Problem 30 Prove that if H is the triangle hypergraph of a graph, then

τ(H) ≤ 2 ν(H) .

The conjecture has been proved for graphs with many edges, and also for graphs which are locally sparse in some sense (e.g., planar graphs). Moreover, it is known that τ ≤ (3 − c) ν holds in general, for some constant c > \frac{3}{23}.

In 3-partite graphs, the stronger bound of τ ≤ (2 − c) ν is also known for some small constant c > 0, but this constant is really small and almost surely quite far from being best possible.

Problem 31 Find better bounds for the supremum of τ/ν in the triangle hypergraphs of 3-chromatic graphs.

Another problem, harder than the first conjecture, is :

Problem 32 Prove the analogous inequality τ ≤ 2 ν for the hypergraph of transitive triangles in an oriented graph.

On the other hand, though the inequality has not yet been proved for cyclically oriented triangles of digraphs either, we expect that stronger inequalities are valid for them.

Problem 33 Determine the smallest constant c with the following property : If an oriented graph contains at most k mutually arc-disjoint cyclic triangles, then all of its cyclic triangles can be destroyed by removing at most ck arcs.

At the other end, triangle families satisfying the equality τ = ν have interesting connections with perfect graphs. But the following question is open, too :

Problem 34 Characterize those families of cyclic triangles in directed multigraphs, where τ = ν holds for every subfamily.

Concerning more general subgraphs of undirected graphs, one can ask :

Problem 35 Let F be any fixed non-bipartite graph. Given a graph G, at most how many edges are needed to cover all subgraphs isomorphic to F in G? More explicitly, prove that the inequality

τ_{F} ≤ (f − 1) ν_{F}

is valid, where f denotes the number of edges in F, provided that F is not bipartite.

If the graph F is bipartite, all but o(n^{2}) edges are needed to cover the copies of F in the complete graph K_{n}, therefore the problem is not really interesting for bipartite graphs.

[38] G. Bacsó – Zs. Tuza : Graph perfectness and triangle families of multigraphs. (to appear)

[39] P. E. Haxell : Packing and covering triangles in graphs. Discrete Math. 195 (1999), 251–254.

10. Largest bipartite subgraphs of graphs

[40] P. E. Haxell – Y. Kohayakawa : Packing and covering triangles in tripartite graphs. Graphs and Combinatorics 14 (1998), 1–10.

[41] Zs. Tuza : A conjecture on triangles of graphs. Graphs and Combinatorics 6 (1990), 373–380.

[42] : Perfect triangle families. Bull. London Math. Soc. 26 (1994), 321–324.

10. Largest bipartite subgraphs of graphs

The Max-Cut optimization problem has been studied in a large number of papers. In this section we mention a couple of unsolved problems for Simple Max-Cut, i.e. where only the number of edges in the cut is counted, or equivalently, all edge weights are assumed to be equal.

The “ Kneser graphs ” constitute one of the most explicitly described graph class in which the size of largest bipartite subgraphs is still unknown in general. The vertex set of the Kneser graph K(n, r) (n > 2r ≥ 4) consists of the r-element subsets of an n-element set S. Two vertices are adjacent if and only if the corresponding two r-sets are disjoint.

Problem 36 Prove or disprove that a bipartite subgraph of K(n, r) with the largest possible number of edges can be constructed for every n and r in the following way. Start with a bipartition S′ ∪ S′′ = S of the base set S. Put the representing vertex of an r-set H ⊂ S into the first vertex class of K(n, r) if H ⊆ S′, and put H into the second class if H ∩S′′ ≠ ∅. Choose |S′| optimally, to obtain the largest possible number of edges between S′ and S′′.

Assuming S = {1, …, n}, it is known that there exists an extremal bipartition of K(n, r) such that two vertices belong to the same partition class whenever the corresponding r-subsets have the same largest element. Perhaps one would expect that it is a matter of routine to derive the above conjecture from this property (while it has been done for n up to about 4.3 r only). On the other hand, however, some situations may require quite a careful analysis. For instance, in K(8, 3), the “ sliced ” partition defined above yields 210 edges, while splitting S into two 4tuples S_{1}, S_{2} and placing a triple in class i if it has more elements in S_{i} than in S_{3−i} (i = 1, 2), generates 208 edges, nearly reaching the former.

A first intuition might be that in graphs without triangles it is easier to optimize the size of a bipartite subgraph than in general (though it isn’t). An old conjecture of Erdős deals with this graph class :

Problem 37 Prove that every triangle-free graph with n vertices can be made bipartite by deleting at most n^{2}/25 edges.

It is known that at most n^{2}/18 + n/2 edges always suffice. We note that a Kneser graph is triangle-free if and only if n < 3r, i.e. within the range for which the size of a largest cut is explicitly known.

One of the many ways to find a fairly large bipartite subgraph in a graph is to start with an arbitrary vertex bipartition V = X∪Y, and then make local improvements if possible. Let k be a fixed natural number. A local k-switch is the operation of selecting two subsets X′ ⊂ X and Y′ ⊂ Y, each of cardinality at most k, and replacing the vertex partition (X, Y) with (X ∪ Y′ \ X′, Y ∪ X′ \ Y′). Call the switch improving if the latter partition generates more edges in the corresponding bipartite graph than the former does. In order to make the algorithm run in polynomial time, we restrict our attention to k constant.

Problem 38 Given k, determine the largest constant c = c(k) such that in every connected graph with n vertices and m edges, a bipartite subgraph with at least

\frac{1}{2}m + cn − o(n)

edges can be found along a sequence of improving local k-switches, from an arbitrary initial bipartition.

It has been proved that every c(k) is strictly smaller than 1/4, but its exact value seems to be unknown for each k. In particular, one should find the smallest k with c(k) > 0. (Maybe already c(1) > 0 ? )

Finally, we mention a problem on graphs of high symmetry. A graph is called vertex- (edge-) transitive if for any two of its vertices (edges) there exists an automorphism that maps one specified vertex (edge) to the other.

Problem 39 Let G be a vertex- (edge-) transitive graph with k vertices (edges). Suppose further that G is 4-chromatic. How many vertices (edges) — as a function of k — have to be deleted in order to make G bipartite ?

If G is not 4-colorable, then this number is known to be at least \sqrt{k}, hence it tends to infinity with k. On the other hand, for 3-colorable graphs nothing like this can be true, because the odd cycles are transitive and they become bipartite by deleting just one edge. No results are known about the 4-chromatic case.

11. Weighted edge covering with complete subgraphs

[43] R. Ahlswede – G. O. H. Katona : Graphs with maximal number of adjacent pairs of edges. Acta Math. Acad. Sci. Hungar. 32 (1978), 97–120.

[44] S. Bylka – A. Idzik – Zs. Tuza : Maximum cuts : Improvements and local algorithmic analogues of the Edwards–Erdős inequality. Discrete Math. 194 (1999), 39–58.

[45] P. Erdős – R. Faudree – J. Pach – J. Spencer : How to make a graph bipartite. J. Combinatorial Theory B 45 (1988), 86–98.

[46] N. V. Ngoc – Zs. Tuza : Linear-time approximation algorithms for the Max Cut problem. Combin. Probab. Comput. 2 (1993), 201–210.

[47] S. Poljak – Zs. Tuza : Maximum bipartite subgraphs of Kneser graphs. Graphs and Combinatorics 3 (1987), 191–199.

[48] : Bipartite subgraphs of triangle-free graphs. SIAM Journal on Discrete Mathematics 7 (1994), 307–313.

[49] : Maximum cuts and large bipartite subgraphs. “ Combinatorial Optimization ” (W. Cook et al., eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science 20, Amer. Math. Soc. (1995), 181–244.

Slightly longer version : The Max-Cut problem — A survey. Preprint, Academia Sinica, Taipei, Taiwan, 1993, 91 pages.

[50] V. Rödl – Zs. Tuza : On color critical graphs. J. Combinatorial Theory B 38 (1985), 204–213.

11. Weighted edge covering with complete subgraphs

Introducing a weight function on some sample graphs, one goal is to find a partition of the edge set into subgraphs isomorphic to the samples, with as mall total weight as possible. The easiest-looking case is that of edges and triangles, but already this leads to considerable difficulties.

Problem 40 Prove that every n-vertex graph has a partition of total weight at most (\frac{1}{2} + o(1)) n^{2} into edge-disjoint triangles of weight 3 and edges of weight 2.

This problem can be transformed to one concerning the packing number of triangles :

Problem 41 If a graph has n vertices and \frac{n^{2}}{4} +k edges, then it contains at least \frac{2}{3}k − o(n^{2}) mutually edge-disjoint triangles.

In a stronger form, it is expected that the “ o(n^{2}) ” term can be replaced by a (possibly quite small) absolute constant.

The problem has also been raised in a more general form, with complete subgraphs of any given size :

Problem 42 Let r ≥ 4 be a fixed integer. Does every graph with n vertices and \frac{r−2}{2r−2}n^{2} + k edges contain at least \frac{2}{r}k − o(n^{2}) mutually edge-disjoint complete subgraphs with r vertices ?

Perhaps r = 4 will admit an easier solution than the case of triangles. We don’t know how thoroughly some potential counterexamples for r > 3 have been investigated.

Paul Erdős (private communication) suggested that perhaps the following variant, where complete subgraphs of any size are allowed to occur, is also valid.

Problem 43 Assuming that each complete subgraph K_{i} has weight i−1 (i = 2, 3, …), prove that every graph on n vertices admits a partition into edge-disjoint subgraphs K_{i} of total weight at most ⌊\frac{n^{2}}{4} ⌋.

Győri remarks that even the following rather particular case is unsolved :

Problem 44 If G is a K_{4}-free graph with n vertices and ⌊\frac{n^{2}}{4} ⌋+k edges, does then G contain at least k mutually edge-disjoint triangles ?

On the other hand, interestingly enough, if the K_{i} are supposed to have weight i, an edge partition of total weight at most n^{2}/2 can be obtained by successively selecting a largest complete subgraph in each step. It is not known, however, whether the same is true if inclusionwise maximal complete subgraphs are selected one by one.

Certainly, edge covers are sometimes easier to find than edge partitions. For instance, it is proved that the number of edges in a largest triangle-free subgraph is an upper bound on the smallest number of triangles and edges whose union is the entire edge set. On the other hand, it is not known whether that many triangles and edges suffice to partition the edge set.

Pyber suggests that the folowing variant of Problem 40 may be valid for covering (and then it would be tight, not only asymptotically) :

Problem 45 Can the edge set of every n-vertex graph be covered with triangles of weight 3 and edges of weight 2 such that their total weight is at most ⌊\frac{n^{2}}{2} ⌋?

Also, it seems to be open whether the answer to Problem 43 is affirmative if we replace “ partition ” with “ covering. ” Observe, however, that on K_{4}- free graphs the two versions are equivalent ; i.e., an affirmative answer to the problem on covering would imply that a large triangle-packing — as required in Problem 44 — exists as well.

[51] F. R. K. Chung : On the decomposition of graphs. SIAM J. Alg. Disc. Methods 2 (1981), 1–12.

[52] P. Erdős – A. W. Goodman – L. Pósa : The representation of graphs by set intersections. Canad. J. Math. 18 (1966), 106–112.

[53] E. Győri : Edge disjoint cliques in graphs. Sets, graphs and numbers (Budapest, 1991), Proc. Colloq. Math. Soc. János Bolyai 60 North-Holland (1992), 357–363.

[54] E. Győri – A. V. Kostochka : On a problem of G. O. H. Katona and T. Tarján. Acta Math. Acad. Sci. Hungar. 34 (1979), 321–327.

[55] E. Győri – Zs. Tuza : Decompositions of graphs into complete subgraphs of given order. Studia Sci. Math. Hungar. 22 (1987), 315–320.

[56] J. Kahn : Proof of a conjecture of Katona and Tarján. Priodica Math. Hungar. 12 (1981), 81–82.

[57] J. Lehel – Zs. Tuza : Triangle-free partial graphs and edge covering theorems. Discrete Math. 39 (1982), 59–65.

[58] S. McGuinness : Greedy maximum-clique decompositions. Combinatorica 14 (1994), 335–343.

[59] L. Pyber : Covering the edges of a graph by.... Sets, graphs and numbers (Budapest, 1991), Proc. Colloq. Math. Soc. János Bolyai 60 North-Holland (1992), 583–610.

12. Strongly triangle-free subgraphs

12. Strongly triangle-free subgraphs

The conjecture to be discussed next would be another strong generalization of Turán’s theorem on triangles. For graphs G, let us introduce the notation

• α_{1}(G) = maximum number of edges, no two of them occurring in any triangle of G; and

• τ_{1}(G) = minimum number of edges, each triangle of G containing at least one of them.

Problem 46 Prove that

α_{1}(G) + τ_{1}(G) ≤ ⌊\frac{n^{2}}{4} ⌋

holds for every graph G on n vertices.

There are lots of examples for tightness ; for instance, K_{n}, K_{⌊n/2⌋,⌈n/2⌉}, K_{n} − 4K_{n/4} if n is a multiple of 4, etc.

It is a very natural question whether the above inequality has analogues for subgraphs different from triangles :

Problem 47 Find a “ nice ” generalization of the above inequality for other types of graphs, too.

This problem is open to such a large extent that for F ≠ K_{3} it is not even clear what one might expect as a reasonable formula to prove ! Note that if F has f edges, then f − 1 pairs of the parameters α_{i}, τ_{i} can be defined (at most i edges in any copy of F, and at least i edges selected from each copy of F, for i = 1, 2, …, f − 1).

As regards lower bounds, one of the open questions is :

Problem 48 Prove that the function

min_{{G \atop |E(G)|=m}} \frac{α_{1}(G) + τ_{1}(G)}{m^{2/3}}

tends to a constant as m → ∞, and determine its value.

It is known that for the above ratio,

lim inf_{m→∞} ≥ \frac{1}{\sqrt[3]{6}} ,  lim sup_{m→∞} ≤ ^{3} \sqrt{4} .

Concerninig maximum, professor Gallai (private communication) expected that some interesting upper bounds may be valid for α_{1} + 2 τ_{1}. We mention two related questions of similar form.

13. Excluded cycle lengths, chromatic number, and orientations

Problem 49 Can

\frac{α_{1}(G) + 2τ_{1}(G)}{|E(G)|}

be arbitrarily close to 3/2 ?

Problem 50 Can

\frac{min \{α_{1}(G), τ_{1}(G)\}}{|E(G)|}

be arbitrarily close to 1/2 ?

Both constants 3/2 and 1/2 are upper bounds, because all triangles (and, more generally, all odd cycles) can be destroyed by the removal of fewer than half of the edges.

[60] P. Erdős – T. Gallai – Zs. Tuza : Covering and independence in triangle structures. Discrete Math. 150 (1996), 89–101.

13. Excluded cycle lengths, chromatic number, and orientations

One of the basic facts in graph theory is that a graph is bipartite if and only if it contains no odd cycles. This may admit generalizations in the following way.

Problem 51 Find pairs q, r of integers with the following property :

If a graph does not contain any cycles of length ≡ r (mod q), then its chromatic number is bounded above by a function of q.

For the residue class r = 1, the inequality χ(G) ≤ q is known to be valid, for every q. (The above-mentioned case of bipartite graphs means q = 2.) This result has some interesting algorithmic aspects as well.

A more general — and maybe too hard — qeustion is :

Problem 52 For each integer k ≥ 2, characterize the sets R of natural numbers such that every graph of chromatic number greater than k contains a cycle of length belonging to R, and R is minimal under inclusion with respect to this property.

Clearly, for k = 2, the unique minimal R consists of all odd numbers ≥ 3. But for larger k, perhaps the residue classes mentioned above are not minimal sets anymore.

14. The Acyclic Orientation Game

As regards orientations, it is also known that if G admits an orientation where each underlying cycle C of length |C| ≡ 1 (mod q) contains at least |C|/q oriented edges in each direction, then again the chromatic number of G does not exceed q.

Problem 53 For which other values of r is an analogous result valid ?

It would also be interesting to know what happens if we restrict ourselves to some particular types of orientations. One example is :

Problem 54 Find minimal sets R such that in every strongly connected orientation of every graph with chromatic number greater than k there is a directed cycle of length belonging to R.

For χ(G) > k it is known that a directed cycle of length at least k must occur in every strong orientation ; but perhaps more restricted versions of this theorem can also be proved about the forced cycle lengths.

[61] J. A. Bondy : Disconnected orientations and a conjecture of Las Vergnas. J. London Math. Soc. (2) 14 (1976), 277–282.

[62] T. Gallai : On directed paths and circuits. Theory of Graphs (P. Erdős and G. O. H. Katona, eds.), Proc. Colloq. at Tihany, Hungary, 1966, Academic Press (1968), 115–118.

[63] G. J. Minty : A theorem on n-colouring the points of a linear graph. Amer. Math. Monthly 67 (1962), 623–624.

[64] R. Roy : Nombre chromatique et plus longs chemins d’un graphe. Rev. AFIRO 1 (1967), 127–132.

[65] Zs. Tuza : Graph coloring in linear time. J. Combinatorial Theory B 55 (1992), 236–243.

14. The Acyclic Orientation Game

The following game is related to the problem of testing — with possibly few questions — whether a coloring of a graph is proper. Two players, Algy and Strategist, play on a graph G as follows. Strategist claims to have created an acyclic orientation of G, and Algy would like to find it. In each step, Algy selects an edge and Strategist tells its orientation. The game is over when Algy can identify a unique acyclic extension of the partial orientation obtained. Algy’s goal is to make the game as short as possible, while Strategist aims at the opposite. Denote by c(G) the number of steps when both play optimally.

Problem 55 Prove that

c(G) ≤ \frac{n^{2}}{4} + o(n^{2})

for every graph on n vertices.

It may even be the case that the term o(n^{2}) can be replaced by an absolute constant.

Call a graph exhaustive if Algy needs to ask about all the edges. It is known that on more than 6 vertices, every exhaustive graph different from the Turán graph has fewer than ⌊\frac{n^{2}}{4} ⌋ edges.

Problem 56 Characterize some “ nice ” classes of exhaustive graphs.

So far, only the exhaustive chordal graphs have been characterized (in terms of forbidden subgraphs ; one needs to exclude subgraphs isomorphic to K_{4} and K_{1}+P_{4}, i.e. the 5-vertex graph where the neighborhood of a vertex of degree 4 is an induced path of length 3). Note that the Hasse diagrams / covering graphs of partially ordered sets all are exhaustive.

Problem 57 Prove that, for every edge probability function p = p(n), Algy needs at most O(n log n) steps on the random graph G_{n,p} with n vertices and edge probability p.

The case of p = 1 (complete graphs) just means sorting n elements. For any positive constant edge probability, the upper bound of O(n log n) has been proved ; but for probabilities tending to zero, only O(n log^{3} n) is known.

Problem 58 How hard is it to decide whether G is exhaustive ?

Note that, though Hasse diagrams are NP-complete to recognize, the larger class of exhaustive graphs might happen to be simpler.

Problem 59 Determine the complexity of finding c(G).

For questions of the type “ Is c(G) ≤ k? ” the membership in NP is not at all clear, and probably not true.

Problem 60 Characterize the graphs G with c(G) ≤ k, for some small fixed values of k.

Though the latter problem is really quite restricted, still a careful analysis may shed light on the nature of c(G) in general.

15. Transversals of uniform hypergraphs

Problem 61 What is the complexity of designing an optimal strategy for each player ?

A reasonable candidate seems to be somewhere around PSPACE.

[66] M. Aigner – E. Triesch – Zs. Tuza : Searching for acyclic orientations of a graph. Discrete Math. 144 (1995), 3–10.

[67] N. Alon – Zs. Tuza : The acyclic orientation game on random graphs. Random Structures and Algorithms 6 (1995), 261–268.

[68] U. Manber – M. Tompa : The effect of the number of Hamiltonian paths on the complexity of a vertex coloring problem. Proc. 25th FOCS (1984), 220–227.

15. Transversals of uniform hypergraphs

One possible setting for upper bounds on the transversal number of uniform hypergraphs is as follows.

Problem 62 For a fixed integer r ≥ 2, find pairs (a, b) such that the inequality

τ(H) ≤ an + bm

is valid for every r-uniform hypergraph H with n vertices and m edges.

For graphs (i.e., r = 2), the situation is completely described, but for r ≥ 3 only very few tight pairs are known (e.g. a = b = \frac{1}{4} for r = 3.) An interesting particular unsolved case is :

Problem 63 Prove that τ(H) ≤ \frac{n}{4} holds whenever H is 6-uniform and 3-regular.

Note that the degree and edge-size conditions above imply that H has precisely n/2 edges, to be covered with half that many vertices. An affirmative answer would have an interesting implication on graph domination, too.

More generally, we ask :

Problem 64 Given r and d, determine the largest possible value of \frac{τ(H)}{|V (H)|} for r-uniform d-regular hypergraphs H.

Problem 65 Given r and d, determine the smallest possible value of \frac{ν(H)}{|V (H)|} for r-uniform d-regular hypergraphs H.

16. Covering and coloring the maximal complete subgraphs

Only very few exact results are known. These problems look quite interesting for Steiner systems of various parameters, too.

[69] N. Alon : Transversal numbers of uniform hypergraphs. Graphs and Combinatorics 6 (1990), 1–4.

[70] V. Chvátal – C. McDiarmid : Small transversals in hypergraphs. Combinatorica 12 (1992), 19–26.

[71] F. C. Lai – G. J. Chang : An upper bound for the transversal numbers of 4-uniform hypergraphs. J. Combinatorial Theory B 50 (1990), 129– 133.

[72] Zs. Tuza : Covering all cliques of a graph. Discrete Math. 86 (1990), 117–126.

Reprinted in : “ Topics on Domination,” Annals of Discrete Math. 48, 1991.

[73] : Matchings and coverings in regular uniform hypergraphs. Ars Combinatoria 29C (1990), 122–129.

[74] : Large partial parallel classes in Steiner systems. Annals of Discrete Math. 52 (1992), 545–548.

[75] Zs. Tuza – P. D. Vestergaard : Domination in partitioned graphs. (to appear.)

16. Covering and coloring the maximal complete subgraphs

At the end of this first part of our problem collection, we deal with two types of problems on cliques, i.e. inclusionwise maximal complete subgraphs with more than one vertex. (Isolated vertices are irrelevant in the present context.) The clique hypergraph H_{C} = H_{C}(G) of graph G = (V, E) has the same vertex set V as G, and a subset is an edge in H_{C} if and only if it induces a clique in G. We denote by

• τ_{C}(G) the transversal number of H_{C}(G), i.e. the minimum number of vertices meeting all cliques of G;

• χ_{C}(G) the chromatic number of H_{C}(G), i.e. the smallest number of classes in a vertex partition such that no class contains any clique of G.

Problem 66 Prove that, for every n, the maximum value of τ_{C}(G) over all graphs on n vertices is attained by some triangle-free graph G.

If this problem has an affirmative solution, then finding the corresponding maximum is equivalent to determining the Ramsey numbers r(K_{3}, K_{t}). On the latter, quite strong asymptotic results are known. Nevertheless, the above problem is still open, and quantitatively already the following bound would be of interest.

Problem 67 Prove that, for any sequence of n-vertex graphs G_{n},

\frac{n − τ_{C}(G_{n})}{\sqrt{n}}

tends to infinity as n → ∞.

The conjecture on the existence of triangle-free extremum motivates further interesting questions, e.g. the following one :

Problem 68 Find (asymptotically) tight bounds on the largest number of vertices in a triangle-free induced subgraph of a K_{4}-free graph on n vertices.

The extremal behavior of τ_{C} is not known in some “ popular ” graph classes either.

Problem 69 Determine the supremum of τ_{C}(G)/|V (G)| over all planar graphs G.

The dodecahedron graph shows that the ratio can reach 3/5. The value of 3/5 may happen to be the right answer, nevertheless there are no good upper bounds known.

Problem 70 Prove, without using the Four Color Theorem, that

τ_{C}(G) ≤ \frac{n}{4}

holds for every planar graph G on n vertices.

This would be implied by

Problem 71 Prove, without using the Four Color Theorem, that every planar graph on n vertices contains an independent set of cardinality at least n/4.

The current record, as well as the record 25 years ago, is 2n/9.

Problem 72 Determine the supremum value of τ_{C}(G)/|V (G)| over all perfect graphs G.

This value is at least 5/9, shown by the graph constructed from the 9cycle v_{1}v_{2} … v_{9} by inserting a triangle on the triple {v_{3}, v_{6}, v_{9}}. Let us introduce the temporary notation C_{9}^{Δ} for this graph. Note that C_{9}^{Δ} is planar.

Problem 73 Is τ_{C}(G) ≤ 5|V (G)|/9 for every perfect planar graph ?

Observe further that the clique hypergraph of C_{9}^{Δ} is not 2-colorable.

Problem 74 Does there exist an absolute constant c such that χ_{C}(G) ≤ c holds for every perfect graph G?

So far no 4-chromatic example is known. Gyárfás also asks whether a constant upper bound can be proved for the 2-element edges of the clique hypergraphs of perfect graphs. A non-2-colorable example is again the graph C_{9}^{Δ}.

Problem 75 Describe large graph classes admitting polynomial-time algorithms for computing χ_{C}.

It is not hard to prove that the clique hypergraphs of chordal graphs are 2-colorable. On the other hand, the following two restricted problems are still open.

Problem 76 Prove that if G is a chordal graph on n vertices, such that each of its cliques has at least 4 vertices, then τ_{C}(G) ≤ n/4.

Problem 77 Prove that if G is a chordal graph on n vertices, such that each of its edges is contained in a clique of size at least 4, then τ_{C}(G) ≤ 2n/7.

It is certainly the case, not only in restricted graph classes but also in general, that large cliques make τ_{C} small. In this direction, it would be nice to know some quantitative relations, for example the following one :

Problem 78 How large values k = k(n) can ensure that if all cliques of an n-vertex graph G have at least k vertices, then τ_{C}(G) ≤ n − cn holds for some absolute constant c?

In particular, can we choose k = o(n) ? Or, is k = O(n^{α}) already sufficient, with some fixed α < 1 ?

[76] M. O. Albertson : A lower bound for the independence number of a planar graph. J. Combinatorial Theory B 20 (1976), 84–93.

[77] T. Andreae : On the clique-transversal number of chordal graphs. Discrete Math. 191 (1998), 3–11.

[78] T. Andreae – C. Flotow : On covering all cliques of a chordal graph. Discrete Math. 149 (1996), 299–302.

[79] T. Andreae – M. Schughart – Zs. Tuza : Clique-transversal sets of line graphs and complements of line graphs. Discrete Math. 88 (1991), 11–20.

[80] G. Bacsó – S. Gravier – A. Gyárfás – M. Preissmann – A. Sebő : Colouring the maximal cliques of graphs. Manuscript, 1998.

[81] D. Duffus – B. Sands – N. Sauer – R. E. Woodrow : Twocolouring all two-element maximal antichains. J. Combinatorial Theory A 57 (1991), 109–116.

[82] P. Erdős – T. Gallai – Zs. Tuza : Covering the cliques of a graph with vertices. Discrete Math. 108 (1992), 279–289.

Reprinted in : Topological, Algebraical and Combinatorial Structures, Topics in Discrete Mathematics 8, Elsevier, 1992.

[83] J. Kratochvíl – Zs. Tuza : On the complexity of bicoloring clique hypergraphs of graphs. (to appear)

Extended Abstract in : Proc. 11th Annual ACM–SIAM Conference on Discrete

Algorithms, SODA 2000 40–41.

[84] B. Mohar – R. Škrekovski : Grötzsch theorems for the hypergraph of maximal cliques. Electronic J. Combin. 6 (1999), #R26.

See also : [72]

Basic notation and terminology

Some of the general notation is collected below.

• G = (V, E) — graph G with vertex set V and edge set E

• n — the number |V | of vertices

• m — the number |E| of edges

• v_{1}, …, v_{n} — the vertices

• d_{i} — the degree of vertex v_{i} = number of edges incident to v_{i} • d-regular : d_{i} = d for all 1 ≤ i ≤ n

• H — hypergraph (finite set system) ; • vertices : elements of the underlying set V

• edges : members H of H (subsets of V)

• r-uniform : each edge has size |H| = r

• d-regular : each vertex is contained in precisely d edges

• τ(H) — transversal number of H = minimum cardinality of a vertex subset (transversal set) T such that T ∩ H ≠ ∅ for all H ∈ H

• ν(H) — matching number of H = maximum number of mutually vertex-disjoint edges

• independent vertex set : no edge of the (hyper)graph is contained in it

• χ(H) — chromatic number of H = minimum number of indepen-

dent sets whose union is V • k-colorable : χ(H) ≤ k

• k-chromatic : χ(H) = k

• particular types of graphs :

• K_{n} = complete graph, P_{n} = path, C_{n} = cycle (on n vertices)

• K_{p,q} = complete bipartite graph with vertex classes of cardinalities p and q

• G_{n,p} = random graph with n vertices ; each vertex pair is chosen to be an edge with probability p, independently of the other pairs

For concepts not defined here, please consult the references cited.

Key words

Approximability : ⟨3⟩ BIBD (Balanced Incomplete Block Design) : see Steiner system Chromatic number : ⟨2⟩, ⟨10⟩, ⟨13⟩, ⟨14⟩, ⟨16⟩ Complexity higher than NP ? : ⟨14⟩ Covering : ⟨6⟩, ⟨8⟩, ⟨9⟩, ⟨12⟩, ⟨15⟩, ⟨16⟩; see also Partition Cycles in graphs : ⟨3⟩, ⟨4⟩, ⟨13⟩ Degree of vertex : ⟨2⟩, ⟨4⟩, ⟨5⟩ Extremal problem : ⟨2⟩, ⟨4⟩, ⟨5⟩, ⟨10⟩, ⟨11⟩, ⟨12⟩, ⟨14⟩, ⟨16⟩ Linear Program : ⟨6⟩ Matching : ⟨7⟩, ⟨8⟩, ⟨9⟩; see also Partition Max-Cut : ⟨10⟩ NP-hard or in P ? : ⟨1⟩, ⟨2⟩, ⟨3⟩ Oriented graph : ⟨13⟩, ⟨14⟩ Packing : see Matching Partition : ⟨7⟩, ⟨11⟩ Perfect graph classes : ⟨9⟩, ⟨14⟩, ⟨16⟩ Random graphs : ⟨5⟩, ⟨14⟩ Satisfiability : ⟨2⟩ Search problem : ⟨1⟩, ⟨2⟩, ⟨3⟩, ⟨7⟩, ⟨14⟩ Sorting : ⟨14⟩ Steiner system : ⟨6⟩ TFNP, complexity of search in : ⟨1⟩, ⟨3⟩ Topological subgraphs : ⟨4⟩ Transversal : see Covering Triangles in a graph : ⟨6⟩, ⟨9⟩, ⟨11⟩, ⟨12⟩

Recent BRICS Lecture Series Publications

LS-01-1 Zsolt Tuza. Unsolved Combinatorial Problems, Part I. May 2001. viii+30 pp.

LS-98-4 Paola Quaglia. The π-Calculus: Notes on Labelled Semantics. December 1998. viii+16 pp.

LS-98-3 Olivier Danvy. Type-Directed Partial Evaluation. December 1998. Extended version of lecture notes appearing in Hatcliff, Mogensen and Thiemann, editors, Partial Evaluation: Practice and Theory, PEPT ’98 Lecture Notes, LNCS 1706, 1998, pages 367–411.

LS-98-2 Carsten Butz. Regular Categories and Regular Logic. October

1998. LS-98-1 Ulrich Kohlenbach. Proof Interpretations. June 1998.

LS-97-1 Jan Chomicki and David Toman. Temporal Logic in Information Systems. November 1997. viii+42 pp. Full version appears in Chomicki and Saake, editors, Logics for Database and Information Systems, 3:31–70, Kluwer Academic Publishers, 1998.

LS-96-6 Torben Braüner. Introduction to Linear Logic. December 1996. iiiv+55 pp.

LS-96-5 Devdatt P. Dubhashi. What Can’t You Do With LP? December 1996. viii+23 pp.

LS-96-4 Sven Skyum. A Non-Linear Lower Bound for Monotone Circuit Size. December 1996. viii+14 pp.

LS-96-3 Kristoffer H. Rose. Explicit Substitution – Tutorial & Survey. September 1996. v+150 pp.

LS-96-2 Susanne Albers. Competitive Online Algorithms. September 1996. iix+57 pp.

LS-96-1 Lars Arge. External-Memory Algorithms with Applications in Geographic Information Systems. September 1996. iix+53 pp.

LS-95-5 Devdatt P. Dubhashi. Complexity of Logical Theories. September 1995. x+46 pp.

LS-95-4 Dany Breslauer and Devdatt P. Dubhashi. Combinatorics for Computer Scientists. August 1995. viii+184 pp.

LS-95-3 Michael I. Schwartzbach. Polymorphic Type Inference. June 1995. viii+24 pp.