Open Problems - Graph Theory and Combinatorics

collected and maintained by Douglas B. West

Number of problem pages now posted: 38

This site is a resource for research in graph theory and combinatorics. Open problems are listed along with what is known about them, updated as time permits. Individual pages contain such material as title, originator, date, statement of problem, background, partial results, comments, references. Also available is a Glossary of Terms.

Most pages in this directory have not yet been created; so far this is mostly a list of some well-known problems for which more detailed pages will be written later. Its accessibility at this early stage is a plea for contributed material to accelerate its development. The organization of topics roughly follows the four volumes of The Art of Combinatorics under development by D.B. West. Thus the four main headings are Extremal Graph Theory, Structure of Graphs, Order and Optimization, and Arrangements and Methods.
Alternatively, below is a direct search, courtesy of Google. The code provided no longer works as it should, but it has been modified to search in the domain www.math.uiuc.edu. Thus it will usually return some pages that you have no interest in, but it will also find problem pages under this one that contain your search term.

Google

Note: Here is a discussion of the notation for the number of vertices and the number of edges of a graph G.

Contributions!

Contributions for this page are eagerly solicited. This includes contributions of new or old problems, comments, corrections, pointers to solutions, details for pages not yet created, etc. Please send all contributions to Douglas B. West at west@math.uiuc.edu. Contributions will be edited, and contributors will be acknowledged. The web submission form has been disabled due to the large volume of automated spam it attracted. Other directories of open problems pages can be found as follows: Graph Theory, Combinatorics, Optimization. (emphasizing graph theory, combinatorics, number theory, and discrete geometry) is at the Open Problem Garden at Simon Fraser University.

Extremal Graph Theory

Topics in this section include distance, matching and independence, coloring, perfect graphs, classical extremal problems, etc.

Distance in graphs

Diameter

Average distance

Matching and Independence

Matchings and Factors

Independent Sets

Domination

Coloring

Vertex coloring

Edge-coloring

List Coloring

Graph Homomorphism and Circular Coloring

A homomorphism from a graph G to a graph H is a function f: V(G)→V(H) such that the images of adjacent vertices are adjacent. A (k,d)-coloring of G is an assignment of congruence classes modulo k to vertices of G such that adjacent vertices have colors differing by at least d. Such an assignment is a homomorphism from G into the complement of the dth power of a k-cycle. The circular chromatic number χc of G is the minimum ratio k/d such that G has a (k,d)-coloring; the ceiling of this is the ordinary chromatic number. A homomorphism from G into H is an H-coloring of G.

Generalized Coloring

Stronger Coloring Requirements

Hypergraphs

Perfect Graphs and Related Families

Graph Representations

Intersection Graphs

Classical Extremal Problems

Forced Subgraphs

Graph Decomposition

Graph Ramsey theory

anti-Ramsey problems

Structure of Graphs

Topics in this section include existence questions, connectivity, cycles, planarity and topological graph theory, graph minors, integer flows, algebraic graph theory, etc.

Existence questions

Isomorphism

Decomposition

Labelings

Packing

Vertex Degrees

  • Digraph Partition Problem (Thomassen) - There exists a least number f(s,t) such that the vertices of any simple digraph with minimum outdegree at least f(s,t) can be partitioned into two sets inducing subdigraphs with minimum outdegree at least s and at least t, respectively. [It is known that f(1,1)=3.

    Tournaments

    Graph Products

    Connectivity

    Cycles

    Digraphs

    Cycle lengths

    Cages

    A (k,g)-cage is a graph with minimum order among all k-regular graphs with girth g

    Longest paths

    Longest cycles (and Hamiltonian cycles)

    Hamiltonian decomposition

    Definition: A Hamiltonian decomposition is a decomposition of a regular graph into spanning cycles (if the degree is even) or into spanning cycles and a single 1-factor (if the degree is odd).

    Topological Graph Theory

    Subgraphs of Planar Graphs

    Coloring of Graphs on Surfaces

    Parameters of Planar Graphs

    Crossing Number

    The crossing number cr(G) of a graph G is the minimum number of edge-crossings in a drawing of G in the plane. In an optimal drawing, it may be assumed that edges cross at most once, that no vertex is an internal point of an edge, that no three edges share an internal point, and that no two edges are tangent.

    Embeddings on Surfaces

    Graph Minors

    Flows in Graphs

    An integer flow on a graph is a pair consisting of an orientation of the graph and an assignment of integer weights to the edges such that for each vertex the total weight on exiting edges equals the total weight on entering edges. It is a k-flow if all weight have absolute value less than k, and it is nowhere-zero if weight 0 is never used. A graph having a nowhere-zero k-flow is k-flowable; this is a dual notion to k-colorability. Note that every nowhere-zero k-flow is a nowhere-zero k+1-flow.

    Coverings and Embeddings

    Snarks

    Algebraic Graph Theory

    Graphs and Vector Spaces

    Graph Eigenvalues

    Distance-Regular Graphs

    Order and Optimization

    Topics in this section include structure of posets, linear extensions, extremal problems on posets, linear and integer programming, matroids and related topics, etc.

    Structure of Posets

    Antichains and Sperner Theory

    Chain Decompositions

    Lattices

    Structure of Special Families

    Linear Extensions

    Dimension of Partial Orders

    The dimension of a partially ordered set P is the minimum number of linear extensions of P whose intersection is P. That is, it is the minimum number of linear orders on the elements of P such that x < y in P if and only if x < y in each of the linear orders. Equivalently, it is the minimum t such that P is a subposet of Rt under the componentwise order.

    Sorting and Searching

    Extremal Problems

    Order Ideals

    Families of Finite Sets (hypergraphs)

    General Partial Orders

    Incidence Algebra and Möbius Functions

    Linear and Integer Programming

    Packing and Covering

    Network Flow

    Polyhedral Methods

    Matroids and Related Topics

    Matroids

    Antimatroids and Greedoids

    Oriented Matroids

    Arrangements and Methods

    Topics in this section include enumeration, probabilistic methods, numbers and games, designs and coding, discrete geometry, etc.

    Enumeration

    Permutations

    Classical Enumeration

    Asymptotic Enumeration

    Theory of Generating Functions

    Probabilistic Methods

    Random Structures

    Numbers and Games

    Ramsey Numbers

    Combinatorial Number Theory

    Special Combinatorial Configurations

    Combinatorial Gray codes
    Named for the classical Gray code listing binary vectors (cyclically) with one bit change between successive vectors, A combinatorial Gray code is a listing of the objects in a set using only specified changes between successive objects. The last item should also be close to the first, so what is sought is a Hamiltonian cycle in the graph defined by the permitted adjacencies.

    Designs and Coding

    Block Designs

    Coding Theory

    Discrete Geometry

    Configurations of Points

    Hyperplane Arrangements

    Geometric Graphs