Conjecture For all there is an integer such that every digraph of minimum outdegree at least contains a subdivision of a transitive tournament of order .
Conjecture The following statements are equivalent for every endofuncoid and a set : \item is connected regarding . \item For every there exists a totally ordered set such that , , and for every partion of into two sets , such that , we have .
Conjecture Every complete geometric graph with an even number of vertices has a partition of its edge set into plane (i.e. non-crossing) spanning trees.
Problem What is the maximum number of colours needed to colour countries such that no two countries sharing a common border have the same colour in the case where each country consists of one region on earth and one region on the moon ?
Conjecture Let be the disjoint union of the graphs and and let be a surface. Is it true that every optimal drawing of on has the property that and are disjoint?
Problem Two players start at a distance of 2 on an (undirected) line (so, neither player knows the direction of the other) and both move at a maximum speed of 1. What is the infimum expected meeting time (first time when the players occupy the same point) which can be achieved assuming the two players must adopt the same strategy?
Conjecture It has been shown that a -outerplanar embedding for which is minimal can be found in polynomial time. Does a similar result hold for -edge-outerplanar graphs?
Conjecture Let be a simple graph with vertices and list chromatic number . Suppose that and each vertex of is assigned a list of colors. Then at least vertices of can be colored from these lists.
Problem Does the following equality hold for every graph ?
The crossing number of a graph is the minimum number of edge crossings in any drawing of in the plane. In the pairwise crossing number, we minimize the number of pairs of edges that cross.
Question Can either of the following be expressed in fixed-point logic plus counting: \item Given a graph, does it have a perfect matching, i.e., a set of edges such that every vertex is incident to exactly one edge from ? \item Given a square matrix over a finite field (regarded as a structure in the natural way, as described in [BGS02]), what is its determinant?
Question I've been working on this for a long time and I'm getting nowhere. Could you help me or at least tell me where to look for help. Suppose D is an m-by-m diagonal matrix with integer elements all . Suppose X is an m-by-n integer matrix . Consider the partitioned matrix M = [D X]. Obviously M has full row rank so it has a right inverse of rational numbers. The question is, under what conditions does it have an integer right inverse? My guess, which I can't prove, is that the integers in each row need to be relatively prime.
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
For a finite (additive) abelian group , the Davenport constant of , denoted , is the smallest integer so that every sequence of elements of with length has a nontrivial subsequence which sums to zero.
A -page book embedding of consists of a linear order of and a (non-proper) -colouring of such that edges with the same colour do not cross with respect to . That is, if for some edges , then and receive distinct colours.
One can think that the vertices are placed along the spine of a book, and the edges are drawn without crossings on the pages of the book.
The book thickness of , denoted by bt is the minimum integer for which there is a -page book embedding of .
Let be the graph obtained by subdividing each edge of exactly once.
Conjecture There is a function such that for every graph ,
login/create account
there is an integer 
such that every digraph of minimum outdegree at least 
be a 
is connected regarding 
.
and a set 
:
there exists a totally ordered set 
such that 
, 
, and for every partion 
of 
into two sets 
, 
such that 
, we have ![$ X \mathrel{[ \mu]^{\ast}} Y $](/files/tex/0ef560be389646efd1fdde5ebc9afc9ac98ee64e.png)
. 
contains every oriented tree of order ![\[ F_n = 2^{2^{n } } + 1 \]](/files/tex/70ca73d7e82af2fee084a8417e172c58cf78b376.png)
Square-Free?
. Does the fragment 
have the finite model property? 
which is slice, is it a ribbon knot?
is the total graph of a multigraph, then 
. 
and 
and let 
be a surface. Is it true that every optimal drawing of 
(first time when the players occupy the same point) which can be achieved assuming the two players must adopt the same strategy? 
. 
, and let 
be the edge set of a forest chosen uniformly at random from all forests of ![\[ {\mathbb P}(e \in F \mid f \in F}) \le {\mathbb P}(e \in F) \]](/files/tex/1fe7ac9c579238670e3aa16ae401e8194e1c3da3.png)
can be replaced by a smaller value, we can also write the conjecture as, for any positive 
in the hypercube. 
be integers. Set 
and 
for 
. Eventually we have 
; put 
.
, since 
, 
, 
, 
, 
, 
, 
, 
.
.
vertices and list chromatic number 
. Suppose that 
and each vertex of 
colors. Then at least 
vertices of 
contains a complete bipartite subgraph with bipartition 
so that 
? ![\[ \text{pair-cr}(G) = \text{cr}(G) \]](/files/tex/8cece1e00bb0e9fc122e0a5cad0dab2681cf33a4.png)
of a graph 
, we minimize the number of pairs of edges that cross. 
of edges such that every vertex is incident to exactly one edge from 
. Suppose X is an m-by-n integer matrix 
. Consider the partitioned matrix M = [D X]. Obviously M has full row rank so it has a right inverse of rational numbers. The question is, under what conditions does it have an integer right inverse? My guess, which I can't prove, is that the integers in each row need to be relatively prime.
of a graph 
, is the smallest integer 
has a nontrivial subsequence which sums to zero.
of 
and a (non-proper) 
such that edges with the same colour do not cross with respect to 
for some edges 
, then 
and 
receive distinct colours. 
is the minimum integer 
be the graph obtained by subdividing each edge of 
such that for every graph 
Drupal
CSI of Charles University