We are given a complete simple undirected weighted graph and its first arbitrary shortest spanning tree . We define the next graph and find on the second arbitrary shortest spanning tree . We continue similarly by finding on , etc. Let k be the smallest number of disjoint shortest spanning trees as defined above and let be the graph obtained as union of all disjoint trees.
Question 1. What is the smallest number of disjoint spanning trees creates a graph containing a Hamiltonian path.
Question 2. What is the smallest number of disjoint spanning trees creates a graph containing a shortest Hamiltonian path?
Questions 3 and 4. Replace in questions 1 and 2 a shortest spanning tree by a 1-tree. What is the smallest number of disjoint 1-trees creates a Hamiltonian graph? What is the smallest number of disjoint 1-trees creates a graph containing a shortest Hamiltonian cycle?
Let be a simple graph, and for every list assignment let be the maximum number of vertices of which are colorable with respect to . Define , where the minimum is taken over all list assignments with for all .
Conjecture [2] Let be a graph with list chromatic number and . Then
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 .
Problem The valency-variety of a graph is the number of different degrees in . Is the chromatic number of any graph with at least two vertices greater than
Conjecture \item If is a countable connected graph then its third power is hamiltonian. \item If is a 2-connected countable graph then its square is hamiltonian.
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 .
Problem Consider the set of all topologically inequivalent polyhedra with edges. Define a form parameter for a polyhedron as where is the number of vertices. What is the distribution of for ?
The crossing number of is the minimum number of crossings in all drawings of in the plane.
The -dimensional (hyper)cube is the graph whose vertices are all binary sequences of length , and two of the sequences are adjacent in if they differ in precisely one coordinate.
Conjecture Let be a finite family of finite sets, not all empty, that is closed under taking unions. Then there exists such that is an element of at least half the members of .
Let be a positive integer. We say that a graph is strongly -colorable if for every partition of the vertices to sets of size at most there is a proper -coloring of in which the vertices in each set of the partition have distinct colors.
Conjecture If is the maximal degree of a graph , then is strongly -colorable.