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.
login/create account
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 
? 
-connected graph with a Hamilton cycle has a second Hamilton cycle. 
hyperplanes in dimension 
is not greater than 
, determine whether or not 
so that the vertex 
is either the head of both 
and 
or the tail of both 
. A digraph is universal if for every pair of edges 
, there is an alternating walk containing both 
and 
of graphs and an integer 
of 
such that there exists a graph on 
such that 
.
, there exists an integer 
such that if 
is a digraph whose arcs are colored with 
set which is the union of 
is a graph, 
is admissable, and 
is even for every 
, then 
has a faithful cover. 
be positive semidefinite, by Jensen's inequality, it is easy to see ![$ [tr(A^s+B^s)]^{\frac{1}{s}}\leq [tr(A^r+B^r)]^{\frac{1}{r}} $](/files/tex/f5fa90ccf8c1dde9b9bf1f21399b3b5428dab81d.png)
, whenever 
.
, is it still valid?
-degenerate graph (a forest) and a 
-degenerate graph is 
-colourable. 
be a perfect graph on 
contains a complete bipartite subgraph with bipartition 
so that 
? 
is the only 
be a 
so that 
for every matching 
. A strongly minimal cover is a (vertex) cover 
so that 
for every cover 
. 
for some integer 
and fixed colouring 
of 
with 
such that every colouring of the edges of 
vertices whose edges are coloured with at most 
colours. ![\[ w(G) = \max_{H \subseteq G} \left\lceil \frac{ |E(H)| }{ \lfloor \tfrac{1}{2} |V(H)| \rfloor} \right\rceil. \]](/files/tex/d2391343543ce03d861e6eb2f4985d52e309525d.png)
. 
, the sequence in 
consisting of 
copes of 
and 
copies of 
has the fewest number of distinct subsequence sums over all zero-free sequences from 
. 
is a tournament of order 
arc-disjoint transitive subtournaments of order 3. 
is the minimum number of colours in a strong edge-colouring of 
and 
in 
there is an integer 
collinear points or 
, 
so that 
does not contain an odd edge-cut. 
, let 
be the statement that given any exact 
-coloring of the edges of a complete countably infinite graph (that is, a coloring with 
, 
, or 
. 
be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than 
-hardness? 
-
(mod 
) for every vertex 
-flow 
on 
from the edge set of 
, for all 
.
-regular graph 
for every 
with 
odd.
be an integer. If 
. 
, equals the minimum number of colors needed in a total coloring of 
plus one or two. In other words, ![\[\chi''(G)=\Delta(G)+1\ \ or \ \ \Delta(G)+2.\]](/files/tex/d4ea30e930ec20e02c5a03c6322e6d99a6bdb63a.png)
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). 
. 
(along the track) away from every other runner. 
for some filter objects 
, 
. Particularly, is this formula true for 
? 
for some filter objects 
edges whose deletion destroys every triangle. 
a non-negative integer 
which we think of as the amount of gold at 
in 
such that the fundamental group of the complement has an unsolvable word problem? 
? 
Drupal
CSI of Charles University