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.
login/create account
contains every oriented tree of order 
as a subdigraph. 
and graph 
, the number of homomorphisms from 
. 
is the only 
-chromatic double-critical 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 
containing a Hamiltonian path.
let 
be the maximum number of vertices of 
, where the minimum is taken over all list assignments 
for all 
. 
and 
. Then ![\[\frac{\lambda_r}{r}\geq\frac{\lambda_s}{s}.\]](/files/tex/47be18e956355dd433b88b66eabf01a9e3ed5f61.png)
-flow. 
contains 
such that if 
is a digraph whose arcs are colored with 
set which is the union of 
of a graph 
. Is it true that for large enough~
? 
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 
? 
, every 
-diregular oriented graph on at most 
vertices has a Hamilton cycle. 
where 
is the number of vertices. What is the distribution of 
for 
? ![$ p \in [0,1] $](/files/tex/1d076f7332523eb59bd7deae19667f83f0a3b6e0.png)
, we let 
denote a subgraph of 
.
so that 
? 
. 
of 
is the graph whose vertices are all binary sequences of length 
-degenerate graph (a forest) and a 
-degenerate graph is 
-colourable. 
generators and exponent 
be a finite family of finite sets, not all empty, that is closed under taking unions. Then there exists 
such that 
is the maximal degree of a graph 
-colorable. 
Drupal
CSI of Charles University