Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G=(V,E) be an Eulerian graph with minimum degree at least 4, and let W be a closed Eulerian walk of G. Is it true that G has a cycle decomposition such that no pair of consecutive edges of W appear in the same cycle of the…
The following definition gives what we conjecture is the correct function a(H) for such a local graph removal lemma. The report passage is retained verbatim as the relevant context for this extracted problem.
Therefore, the focus is on open questions that we explain now and that were not advertised previously. • Could it be that for all Burling graph H, graphs with no subdivisions of H are χ-bounded? This is probably far too much, but…
Let V_n be the ground set, and let α(S_1,…,S_m+1) and α(T_1,…,T_m+1) be two partition m-hemimetrics on V_n. Two rays are adjacent when they generate a two-dimensional face of the cone, that is, when they are adjacent in the skeleton of…
Let A⊂R_>0 be algebraically independent, meaning that no nonzero polynomial with rational coefficients vanishes on any finite tuple of distinct elements of A. A finite colouring of R^2 is said to avoid A if no monochromatic pair of points…
Let t:=n(n+1), and define g_1(n):=1, g_j(n):=j/(j-1)!∏_q=1^j-1(jn+q) (j≥ 2). Polynomial-factorization conjecture. There exist polynomials P_k(t,x) in x of degree k, with coefficients rationally depending on t, such that…
Let P_n be the path graph on n vertices, let P_nmathbinsquareP_n be the Cartesian-product square grid, and let DRMVS(G,s;d,b) denote the maximum number of vertices saved in the distance-restricted firefighting process on graph G, starting…
If an infinite graph is C-roughly transitive for some finite C, must it be roughly isometric to a homogeneous metric space? Equivalently, does there exist an infinite roughly transitive graph that is not roughly isometric to any space with…
Let d≥ 2. A graph has VC-dimension at most d when its VC-dimension is bounded by d. Bounded-VC-dimension Erdős–Hajnal conjecture. There exists a constant ε(d) such that every graph on n vertices with VC-dimension at most d contains a…
Let R_vm(k) denote the smallest integer n such that every graph on n vertices contains the edgeless graph E_k as a vertex-minor. The known values for k=2,3,4 are 3, 7, and 11, respectively, and the next unresolved case concerns k=5.…
Let G be a simple graph, and let δ(G) denote its minimum degree. The maximum nullity M(G) is the greatest nullity among matrices associated with G in the maximum nullity problem. Delta Conjecture. For every simple graph G, δ(G) ≤ M(G). The…
Let G be a subcubic graph, meaning that every vertex of G has degree at most 3, and let χ_2(G) denote its 2-ranking number. The 2-ranking conjecture for subcubic graphs. If G is subcubic, then χ_2(G)≤ 6 and equality holds if and only if G…
An r-graph is an r-regular graph G with the property that |δ(X)| ≥ r for every X ⊆ V(G) with odd size. Conjecture χ'(G) ≤ r+1 for every r-graph G.
Let n be a positive integer, and let k_n be an integer depending on n. A graph is biconnected if it has the connectivity property intended in the paper. Bounded multiplicity conjecture. For any positive integer n, there exists k_n such…
Let G be a 3-vertex-connected graph with a 3-edge cut C, so that deleting C gives two connected components Ssqcup T. Let A=G/T and B=G/S be obtained by contracting one side of the cut, replacing it by a 3-valent vertex. 3-edge-cut…
Let K_k be the complete graph on k vertices, let P_n be the path graph on n vertices, and consider the spanning-tree recurrence for the graph product K_k× P_n. Complete-graph product recurrence order conjecture. The recurrence for the…
For graphs H_1,H_2 and the parameter \delta_{H_1,H_2}(\varepsilon) defined by induced-freeness testing, is \delta_{H_1,H_2}(\varepsilon)=\operatorname{poly}(\varepsilon) for every pair; and for every a>0 do there exist H_1,H_2 with…
Let m, n, k be positive integers and a_ijκ rational integers (1≤ i≤ n, 1≤ j≤ m, 1≤κ≤ k). For underlinex=(x_1,…,x_k)∈(R_+^×)^k denote by Γ(underlinex) the following finitely generated subgroup of (R_+^×)^n: Γ(underlinex)= ( ∏_j=1^m ∏_κ=1^k…
The d numbers logα, α^β, α^β^2,…, α^β^d-1 are algebraically independent over Q.
Let P be a lattice polytope and let L_P(t) be its Ehrhart polynomial of degree d, with roots α_i. Vertical strip conjecture. Every root satisfies -d≤ Re(α_i)≤ d-1 for all i. This conjecture concerns a uniform vertical strip containing the…