Conjecture Denote by the number of non-Hamiltonian 3-regular graphs of size , and similarly denote by the number of non-Hamiltonian 3-regular 1-connected graphs of size .
An alternating walk in a digraph is a walk so that the vertex is either the head of both and or the tail of both and for every . A digraph is universal if for every pair of edges , there is an alternating walk containing both and
Question Does there exist a locally finite highly arc transitive digraph which is universal?
Given a finite family of graphs and an integer , the Turán number of is the largest integer such that there exists a graph on vertices with edges which contains no member of as a subgraph.
Conjecture For every finite family of graphs there exists an such that .
Conjecture For every , there exists an integer such that if is a digraph whose arcs are colored with colors, then has a set which is the union of stables sets so that every vertex has a monochromatic path to some vertex in .
Let be a hypergraph. A strongly maximal matching is a matching so that for every matching . A strongly minimal cover is a (vertex) cover so that for every cover .
Conjecture If is a (possibly infinite) hypergraph in which all edges have size for some integer , then has a strongly maximal matching and a strongly minimal cover.
Conjecture For every fixed and fixed colouring of with colours, there exists such that every colouring of the edges of contains either vertices whose edges are coloured according to or vertices whose edges are coloured with at most colours.
Conjecture For every , the sequence in consisting of copes of and copies of has the fewest number of distinct subsequence sums over all zero-free sequences from of length .
A strong edge-colouring of a graph is a edge-colouring in which every colour class is an induced matching; that is, any two vertices belonging to distinct edges with the same colour are not adjacent. The strong chromatic index is the minimum number of colours in a strong edge-colouring of .
Let be a set of points in the plane. Two points and in are visible with respect to if the line segment between and contains no other point in .
Conjecture For all integers there is an integer such that every set of at least points in the plane contains at least collinear points or pairwise visible points.
Conjecture For , let be the statement that given any exact -coloring of the edges of a complete countably infinite graph (that is, a coloring with colors all of which must be used at least once), there exists an exactly -colored countably infinite complete subgraph. Then is true if and only if , , or .
Conjecture Can the approximation ratio be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than -hardness?
Conjecture A total coloring of a graph is an assignment of colors to the vertices and the edges of such that every pair of adjacent vertices, every pair of adjacent edges and every vertex and incident edge pair, receive different colors. The total chromatic number of a graph , , equals the minimum number of colors needed in a total coloring of . It is an old conjecture of Behzad that for every graph , the total chromatic number equals the maximum degree of a vertex in , plus one or two. In other words,
For a graph , let denote the cardinality of a maximum cycle packing (collection of vertex disjoint cycles) and let denote the cardinality of a minimum feedback vertex set (set of vertices so that is acyclic).
Conjecture Suppose runners having distinct constant speeds start at a common point and run laps on a circular track with circumference 1. Then for any given runner, there is a time at which that runner is distance at least (along the track) away from every other runner.
Setup Fix a tree and for every vertex a non-negative integer which we think of as the amount of gold at .
2-Player game Players alternate turns. On each turn, a player chooses a leaf vertex of the tree, takes the gold at this vertex, and then deletes . The game ends when the tree is empty, and the winner is the player who has accumulated the most gold.