Unsolved Combinatorial Problems, Part I

Zsolt Tuza

May 2001

Abstract:

Contents

1

Subset-Sums Equality

2

Boolean Satisfiability and Hypergraph 2-Coloring with bounded degrees

3

Second Hamiltonian Cycle

4

The number of Hamiltonian subgraphs

5

Local vs. global average degree in graphs

6

Uniform edge cover with triangles

7

Single Input Double Output controllers

8

Ryser's conjecture on $r$-partite hypergraphs

9

Covering the triangles with edges

10

Largest bipartite subgraphs of graphs

11

Weighted edge covering with complete subgraphs

12

Strongly triangle-free subgraphs

13

Excluded cycle lengths, chromatic number, and orientations

14

The Acyclic Orientation Game

15

Transversals of uniform hypergraphs

16

Covering and coloring the maximal complete subgraphs

Available as PostScript, PDF, DVI.