Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G(S) be the distance graph on the integers with generating set S, and let overlineα(S) denote its maximum density of an independent set. Let k>6 with k∉7,10,12,17. The independence ratio conjecture. overlineα(1,6,k)= 3k/7k+7 if k≡…
For the natural finite-to-one map from components of high-dimensional embedding spaces to Maurer--Cartan elements of the associated hairy graph complex, is it related to classical embedding invariants such as the Boechat--Haefliger and…
Let G(n) be the family of graphs with n vertices, 2n-2 edges, and no proper subgraph of minimum degree 3. Erdős–Faudree–Gould–Scheinerman conjecture. Every G∈ G(n) contains cycles of length i for every integer 3≤ i≤ k, where k tends to…
Problem 1. Find a good characterization for undirected graphs having an acyclic orientation so that the in-degree of every node is even. Problem 2. Find a good characterization for undirected graphs G=(V,E) and T⊆ V, having an acyclic…
Finally, it should be mentioned that for all specifically considered graph classes it is already known in the literature that the inequality in Vizing’s conjecture is true. As a result, we do not gain new knowledge on whether Vizing’s…
Let D be an oriented graph, and let δ(D) denote its minimum degree. For positive integers r and s, write vecK_s,s for the consistently oriented complete bipartite graph, and call an antidirected subdivision of a graph restricted when all…
Let overline P_eu^ou(n) be the set of partitions described in the source in which the largest even part has odd multiplicity and every other part has even multiplicity, and let overline p_eu^ou(n) denote its cardinality. Let overline…
Let ξ(n) denote the toroidal covering parameter, and let n range over positive integers. Asymptotic density conjecture. lim_n→∞ξ(2n+1)/2n+1=2/3. The conjecture predicts the limiting density of the parameter along odd arguments. It is…
Conjecture Every simple graph with maximum degree Δ has a proper (Δ+2)-edge-colouring so that every cycle contains edges of at least three distinct colours.
For every k≥1, is s(2^k)=u_k? Is d(2^k)=2^k for k≠2, with d(4)=2?
How many intersections among an arrangement of pseudosegments in the plane must be added as vertices to allow the pseudosegment arrangment to be extended to a pseudoline arrangement? An arrangement of pseudosegments in the plane is a…
Construct efficient pseudorandom functions from ideal-lattice problems.
Abstract. Graph theory is a quickly developing area of mathematics, with an increasing number of connections to various parts of mathematics and computer science. The workshop aimed at bringing together a broad range of researchers at…
Let S be the Kolakoski sequence and let SR(S) denote its set of subrows. An ∞-regular subrow is a subrow that is k-regular for every k. Nonexistence conjecture. There are no ∞-regular subrows in SR(S). This conjecture would imply the…
Can the edges of any graph be covered by at most 2ν triangles, where ν is the maximum size of a triangle packing?
Let G be a connected undirected simple graph with at least 3 vertices, and let U⊆ V(G). Define the U-nucleus complex by Δ^G_U=E(G)∖ E(N):N∈N(G), U⊆ V(N), where N(G) is the set of nuclei of G. Dorpalen-Barry et al.'s homology conjecture.…
Find an attack that breaks the pairing-based cryptographic system discussed in the slides, or establish its resistance to known attacks.
Use a baby-step/giant-step infrastructure framework to speed infrastructure discrete logarithms or point counting by a polynomial factor.
Does there exist ε>0 and d₀ such that every graph G with minimum degree δ(G)≥d₀ satisfies χ′_g(G)≥(1+ε)δ(G), where χ′_g(G) is the game chromatic index?
Let C be a finite or countable graph with no isolated vertices. Decompose C into its blocks, where each block is a 2-connected component, and let tilde C be the underlying forest whose vertices are the blocks of C, with adjacency…