Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
All graphs here are finite, simple and undirected. For a graph G write V(G) for its vertex set, E(G) for its edge set, n=|V(G)|, and Δ(G) for its maximum degree. Call G overfull if |E(G)| > Δ(G)⌊ |V(G)|/2 ⌋ . Let χ'(G) denote the chromatic…
Let G^c be a 2-connected c-edge-colored multigraph on n vertices, where n≥ 10 and c≥ 3. Let rd(G^c) denote its rainbow degree and let m be its number of edges. Proper Hamiltonian cycle conjecture. If rd(G^c)=c and m≥ cbinomn-22+4c+1, then…
Let G be a graph on 2n vertices whose edge set is decomposed into perfect matchings M_1, M_2, and M_3, and let a_1, a_2, and a_3 be non-negative integers satisfying a_1+a_2+a_3=n-1. A component of G is assumed not to be isomorphic to K_4.…
Conjecture If G is a connected graph on n vertices, then c_k(G) ≥ d_k(G) for k = 1, 2, …, n-1.
Let U and U' be unicyclic graphs with the same degree sequence. A 2-switch is an edge-switching operation on a graph. Transition conjecture. There is a sequence of 2-switches transforming U into U' such that every intermediate graph is…
For a positive integer n, let D(n) denote its set of divisors and let τ(n)=|D(n)|. Say that n is strongly matchable if every coprime arithmetic progression of τ(n) integers admits a coprime matching to D(n). Say that n is an M-number if it…
Let S_n be the symmetric group, let w,w'in S_n, and let r(w) and r(w') be their rank matrices. Write T_w for the tangent cone of the Schubert variety associated with w, and call an entry of a rank matrix a pillar entry in the sense of the…
Let C_3 be the triangle and let P_n be the path on n vertices. Write tilder(C_3,P_n) for the minimum number of rounds in the online size Ramsey game in which Builder forces either a red copy of C_3 or a blue copy of P_n. Conjecture on the…
Let G be a bicoloured graph with no isolated vertices and no twins, where twins are vertices having identical relevant neighbourhoods. Let [G] denote the parity class of G, and let a complementation set be as defined in the paper.…
Let G_m,n be the grid in question, and let a shifted k-subgrid mean a k-subgrid satisfying the paper's shift-pattern condition. Prime-order balanced coloring conjecture. For prime k, there exists a k-coloring of G_k^2,k^2 with shift…
Is the shortest vector problem on ideal or cyclic lattices NP-hard, either exactly or under approximation?
Let G be a graph. A function f:V(G)→[0,1] is good if, for every perfect induced subgraph P of G, ∑_v∈ V(P) f(v)≤ 1. For α≥ 1, the graph G is α-narrow if, for every good function f, ∑_v∈ V(G) f(v)^α≤ 1. Narrowness conjecture. For every…
Let k≥ 3 and define g_k(n) to be the minimal N such that 1,…,N contains some A of size lvert Arvert=n such that ⟨ A⟩ = ∑_a∈ Aε_aa: ε_a∈ 0,1 contains no non-trivial k-term arithmetic progression. Estimate g_k(n). In particular, is it true…
For a graph H, an H-deletion-saturated graph is an H-free graph G with E(G)≠∅ such that, for every e∈ E(G), the graph G-e is not H-free. A graph H is deletion-normal if there exists an H-deletion-saturated graph. Likewise, H is…
Give an algorithm and/or a good characterization to decide if a red-blue edge-coloured bipartite graph contains a perfect matching with exactly k red edges.
Let G be a very well covered graph, and for s∈N let J_s(G) denote its s-th jet graph. A graph is very well covered if all its minimal vertex covers have the same cardinality and this cardinality is half the number of vertices. Jet-graph…
Let G be a graph with chromatic number [?] and let S⊆ V(G) be colorful if every proper χ(G)-coloring of G assigns all χ(G) colors to vertices in S. An S-rooted K_t-minor is a model (B_i)_i=1^t of K_t in G such that B_i∩ S≠∅ for every…
Let S be a finite string of heads and tails, let s be its total number of heads and tails, and let E(S) denote the expected number of fair-coin flips needed to produce S. Assume S∉H^k,T^k. Powers-of-two conjecture. The expected value E(S)…
Let L be a frequency square of type F(mλ;λ^m). A balanced diagonal conjecture asserts that if (m-1)λ is even, then L contains a balanced diagonal. The paper establishes this for m∈1,2,3 and gives constructions and observations supporting…
Let P=2,3,5,7,11,… denote the set of prime numbers, i.e. the integers p>1 whose only positive divisors are 1 and p. For every even integer n>2 there exist p,q∈P with n=p+q, where p and q are not required to be distinct (so that, for…