Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
A natural graph is a simple graph whose vertex set is a finite subset of N. Two infinite permutations of N are G-different if, for some coordinate i∈N, the two entries at that coordinate are the endpoints of an edge of G. Let κ(G) be the…
Is it true that, for every bipartite graph G, there exists some α∈ [1,2) and c>0 such that ex(n;G)~ cn^α? Must α be rational?
Let S^2 be the unit 2-sphere. Spherical coloring conjecture. There exists a map q:S^2 → ± 1, ± 2, ± 3, ± 4 such that antipodal points of S^2 receive opposite values, and any three points equidistant on a great circle have values summing to…
Let G be a planar trivalent graph, and let T_G denote its Tait polynomial. Tait polynomial four-colorability conjecture. The graph G is 4-colorable if and only if T_G(1)>0. The source presents this as conditional on positivity properties…
Let S be the class of series-parallel graphs. Biro, Collado and Zamora's conjecture. ^α_ω( S)=frac 1 2. The indeque ratio measures the asymptotic minimum proportion of vertices that can be covered by an indeque set in a graph class. The…
Let G=(V,E) be a simple undirected graph. A tree is an acyclic, connected graph. Its line graph L(G) has vertex set E, with distinct e,fnin E adjacent exactly when e and f are incident in G. Define the iterated line graphs by L^(0)(G)=G,…
What kinds of numerical data or invariants should be extracted from very large graphs, such as protein-interaction graphs, to describe useful structural information?
Let G be a nontrivial connected graph. Let μ^*(G) denote the minimum cardinality of a maximal matching, and let H(G) denote the harmonic index of G. TxGraffiti's conjecture. If G is a nontrivial connected graph, then μ^*(G)≤ H(G), and this…
Let n≥ 4 be odd, let C_n be the cyclic graph on n vertices, and let D_n be the graph shown in Figure~. Two graphs are independence equivalent when they have the same independence polynomial. Beaton–Brown–Cameron conjecture. If 3notvert n,…
For a metric graph with infinitely many edges and Kirchhoff Laplacian H, find geometric or combinatorial criteria guaranteeing self-adjointness, and determine the deficiency indices and self-adjoint extensions when self-adjointness fails.
Let M be a map on the torus, meaning an embedding of a graph in the torus whose faces are disks meeting pairwise only in a vertex or an edge. A map is 4-connected when its underlying graph remains non-trivially connected after the removal…
There exists some constant c>0 such that R(C_4,K_n) ≪ n^2-c.
A linear forest is a forest in which every component is a path. For a graph H, an H-free graph is a graph with no induced subgraph isomorphic to H; a class is intersectionwise self-χ-guarding when it has the property defined in the paper.…
Is it true that, for k≥ 2, ex(n;C_2k-1,C_2k)=(1+o(1))(n/2)^1+1/k.
Matrix Spencer Given matrices A_1,...,A_n ∈R^n× n satisfying ||A_i||_op ≤ 1 where ||.||_op is the operator norm of matrices. Do there exists signs ε_1,...,ε_n∈-1,1 s.t. ||∑_i=1^nε_i A_i || =O(√n).
Let H be a connected triangle-free graph. A graph H is 2-Ramsey-simple when s_2(H)=2(δ(H)-1)+1, where s_2(H) is the minimum degree that can occur in a minimal 2-Ramsey graph for H. Grinshpun's conjecture. Every connected triangle-free…
Let G be a connected bridgeless cubic graph of order at most 8k+8 that does not admit any 3-edge-coloring. Strengthened circular-flow conjecture. Φ_c(G) ≥ 4+1/k. This conjecture strengthens the lower bound of Lukot'ka and Škoviéra for the…
Work efficiently with the testing characters and principal homogeneous spaces without constructing them explicitly.
Let G be a graph on n vertices, and let C be a positive constant. A cycle with linearly many chords is a cycle on [200~ℓ vertices having at least [201~ℓ/2 chords. Cycle-with-chords conjecture. If G has average degree at least Cloglog(n),…
An odd subdivision of a graph G is a graph obtained from G by replacing each edge by a path of odd length. For a positive integer s, a graph is K_s,s-free if it contains no subgraph isomorphic to the complete bipartite graph K_s,s.…