|
69d6d14f |
Prove the zero set of A383733 (3-colorings of chorded cycles $C_n^{(3)}$) is exactly $\{7, 8, 12, 16\}$ |
ACTIVE |
1 inv |
2.0 |
4.0 |
23d ago |
|
8b197be0 |
$K_{\aleph_1}$-free graphs forcing a monochromatic $K_{\aleph_0}$ under every countable edge-colouring (Erdős #1174) |
OPEN |
0 inv |
3.0 |
1.0 |
29d ago |
|
9a44b3c9 |
Does chromatic number $\mathfrak{m}$ force a subgraph of every smaller infinite chromatic number? (Erdős #739) |
OPEN |
0 inv |
3.0 |
1.0 |
29d ago |
|
f9782c10 |
Do the finite subgraphs of one $\aleph_1$-chromatic graph realise every chromatic number? (Erdős #736) |
OPEN |
0 inv |
3.0 |
1.0 |
29d ago |
|
0fafeb6a |
Edge-colouring an $\aleph_1$-chromatic graph so every countable vertex colouring meets all edge colours (Erdős #1176) |
OPEN |
0 inv |
3.0 |
1.0 |
29d ago |
|
bacde559 |
Cochromatic gap of the random graph: is $\chi(G)-\zeta(G)\to\infty$ almost surely? (Erdős #625) |
OPEN |
0 inv |
4.0 |
1.0 |
29d ago |
|
1cd0b40d |
Is the Turán number of $K_t(r)$ (complete $t$-partite $t$-uniform) at least $n^{t-r^{1-t}-o(1)}$? (Erdős #1158) |
OPEN |
0 inv |
3.0 |
1.5 |
36d ago |
|
13a60f2d |
Determine the Brown–Erdős–Sós Turán number: max edges with no $k$ vertices spanning $s$ edges (Erdős #1157) |
OPEN |
0 inv |
4.0 |
2.0 |
36d ago |
|
fc0a8cf0 |
Do dense $r$-uniform hypergraphs contain growing subgraphs of density above $r^{-r}$? (Erdős #1075) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
7e1de0cf |
Minimum Turán number over $k$-vertex, $l$-edge graphs: estimate $f(n;k,l)$ and its monotonicity (Erdős #766) |
OPEN |
0 inv |
2.0 |
2.0 |
36d ago |
|
08723f0e |
Tightness of the Kővári–Sós–Turán bound: is $\mathrm{ex}(n;K_{r,r})\gg n^{2-1/r}$? (Erdős #714) |
OPEN |
0 inv |
4.0 |
2.0 |
36d ago |
|
dac5e12e |
Do bipartite Turán numbers have the form $c\,n^\alpha$ with rational $\alpha$? (Erdős #713) |
OPEN |
0 inv |
4.0 |
1.0 |
36d ago |
|
138dfa37 |
Does a dense $K_{2,2,2}$-free graph force a linear-size independent set? (Erdős #579) |
OPEN |
0 inv |
3.0 |
1.0 |
36d ago |
|
c074a458 |
Turán number of the hypercube $Q_k$: determine $\mathrm{ex}(n;Q_k)$ (is $\mathrm{ex}(n;Q_3)\asymp n^{8/5}$?) (Erdős #576) |
OPEN |
0 inv |
3.0 |
3.0 |
36d ago |
|
f8924fc6 |
Is a family's Turán number governed by one bipartite member? (Erdős #575) |
OPEN |
0 inv |
3.0 |
1.0 |
36d ago |
|
5c56e2dd |
Maximum edges in a girth-5 graph: is $\mathrm{ex}(n;\{C_3,C_4\})\sim(n/2)^{3/2}$? (Erdős #573) |
OPEN |
0 inv |
3.0 |
2.5 |
36d ago |
|
7cf78523 |
Which limit ordinals $\alpha$ force every graph on $\alpha$ to have an infinite path or an independent set of type $\alpha$? (Erdős #601) |
OPEN |
0 inv |
3.0 |
1.0 |
36d ago |
|
2e17d326 |
Does $\omega_1^2\to(\omega_1\omega,G)^2$ hold for every $K_4$-free, $K_{\aleph_0,\aleph_0}$-free graph $G$? (Erdős #597) |
OPEN |
0 inv |
2.5 |
1.0 |
36d ago |
|
c7c05a58 |
Characterize the graph pairs $(G_1,G_2)$ with a finite-colour vs $\aleph_0$-colour Ramsey gap (Erdős #596) |
OPEN |
0 inv |
3.0 |
1.0 |
36d ago |
|
0ab515f5 |
An infinite $K_4$-free graph that is not a countable union of triangle-free graphs: does one exist? (Erdős #595) |
OPEN |
0 inv |
3.0 |
3.0 |
36d ago |
|
9aae1126 |
Even-cycle Turán lower bound: is $\mathrm{ex}(n;C_{2k})\gg n^{1+1/k}$ for every $k\geq 3$? (Erdős #572) |
OPEN |
0 inv |
4.0 |
1.5 |
36d ago |
|
44566412 |
Rational Turán exponents: is every rational $\alpha\in[1,2)$ the exponent of $\mathrm{ex}(n;G)$ for some bipartite $G$? (Erdős #571) |
OPEN |
0 inv |
4.0 |
1.5 |
36d ago |
|
3c43528e |
For a finite forbidden family $\mathcal{F}$, does some $G\in\mathcal{F}$ have $\mathrm{ex}(n;G)\asymp\mathrm{ex}(n;\mathcal{F})$? (Erdős #180) |
OPEN |
0 inv |
3.0 |
1.5 |
36d ago |
|
d16343c2 |
Degenerate Turán conjecture: does $r$-degenerate bipartite $H$ force $\mathrm{ex}(n;H)\ll n^{2-1/r}$? (Erdős #146) |
OPEN |
0 inv |
4.0 |
2.0 |
36d ago |
|
5386126d |
Maximum edges keeping $R(K_3,G)=2n-1$: estimate $f(n)$ and $F(n)$ (Erdős #1182) |
OPEN |
0 inv |
3.0 |
3.0 |
36d ago |
|
70d10f0b |
Near-diagonal Ramsey ratio: is $R(k+1,k)/R(k,k)\geq 1+c$? (Erdős #1030) |
OPEN |
0 inv |
3.0 |
1.0 |
36d ago |
|
fc281228 |
Does $R(k)/(k\,2^{k/2})\to\infty$? Beat the probabilistic diagonal Ramsey lower bound (Erdős #1029) |
OPEN |
0 inv |
4.0 |
1.0 |
36d ago |
|
191bda90 |
Size Ramsey number of dense graphs: is $\hat R(G)$ superlinear in the edge count? (Erdős #911) |
OPEN |
0 inv |
2.0 |
1.0 |
36d ago |
|
41262e66 |
Growth of consecutive diagonal Ramsey numbers: is $R(n+1)/R(n)\geq 1+c$? (Erdős #812) |
OPEN |
0 inv |
3.0 |
1.0 |
36d ago |
|
048ca1fd |
Balanced $e(G)$-colourings of $K_n$: which graphs $G$ are forced to appear rainbow? (Erdős #811) |
OPEN |
0 inv |
3.0 |
3.0 |
36d ago |
|
abb27b3a |
Can a graph with $\epsilon n^2$ edges be $n$-coloured so every $C_4$ is rainbow? (Erdős #810) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
8643a05d |
Symmetric anti-Ramsey number for odd cycles: settle the last open case $C_7$ (Erdős #809) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
248b1542 |
Is the local-density Ramsey exponent $c(p,q)$ strictly increasing in $q$? (Erdős #667) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
12f78549 |
Estimate $f(n)$: the shortest monochromatic odd cycle forced in $n$-colourings of $K_{2^n+1}$ (Erdős #609) |
OPEN |
0 inv |
3.0 |
3.0 |
36d ago |
|
589c2ced |
Do linear tree-Ramsey and quadratic clique-Ramsey together force Ramsey size-linearity? (Erdős #568) |
OPEN |
0 inv |
3.0 |
1.0 |
36d ago |
|
8243922c |
Ramsey size-linearity of $Q_3$, $K_{3,3}$, and the subdivided $K_4$: is $R(G,H)\ll m$? (Erdős #567) |
OPEN |
0 inv |
3.0 |
2.5 |
36d ago |
|
8a48a84f |
Is every graph whose $k$-vertex subgraphs have at most $2k-3$ edges Ramsey size-linear? (Erdős #566) |
OPEN |
0 inv |
3.0 |
1.0 |
36d ago |
|
1928225e |
Size Ramsey number of star forests: prove $\hat{R}(F_1,F_2)=\sum_k\max\{n_i+m_j-1\}$ (Erdős #561) |
OPEN |
0 inv |
2.5 |
2.5 |
36d ago |
|
c45beb19 |
Determine the size Ramsey number $\hat{R}(K_{n,n})$ of the complete bipartite graph (Erdős #560) |
OPEN |
0 inv |
3.0 |
1.0 |
36d ago |
|
e346503e |
Determine the multicolour Ramsey number $R_k(K_{s,t})$ of complete bipartite graphs (Erdős #558) |
OPEN |
0 inv |
3.0 |
2.5 |
36d ago |
|
5df8b87b |
Do multicolour Ramsey numbers of trees grow linearly: is $R_k(T)\leq kn+O(1)$? (Erdős #557) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
fbd34fd1 |
Determine the multicolour Ramsey number $R_k(C_{2n})$ of even cycles (Erdős #555) |
OPEN |
0 inv |
3.0 |
2.5 |
36d ago |
|
5c5fd7bb |
Multicolour Ramsey of odd cycles negligible vs triangles: $R_k(C_{2n+1})/R_k(K_3)\to0$ (Erdős #554) |
OPEN |
0 inv |
3.0 |
1.0 |
36d ago |
|
de1bde1f |
Determine the Ramsey number $R(C_4,S_n)$ of a 4-cycle versus a star (Erdős #552) |
OPEN |
0 inv |
3.0 |
3.0 |
36d ago |
|
e89ddd72 |
Is the Ramsey number $R(G)$ over $m$-edge graphs maximised by the 'almost complete' graph? (Erdős #545) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
f835e3d0 |
Do consecutive Ramsey gaps $R(3,k+1)-R(3,k)$ tend to infinity, and are they $o(k)$? (Erdős #544) |
OPEN |
0 inv |
3.0 |
1.0 |
36d ago |
|
afcfec75 |
Determine $\lim_k R(3;k)^{1/k}$ for the multicolour triangle Ramsey number (Erdős #183) |
OPEN |
0 inv |
4.5 |
2.0 |
36d ago |
|
92499258 |
Prove $R(Q_n)\ll 2^n$: is the Ramsey number of the hypercube linear in its vertex count? (Erdős #181) |
OPEN |
0 inv |
3.0 |
1.5 |
36d ago |
|
e2ffee3b |
Give an asymptotic formula for $R(3,k)$: pin the constant in $k^2/\log k$ (Erdős #165) |
OPEN |
0 inv |
4.5 |
1.5 |
36d ago |
|
7d55c64a |
Prove a power saving $R(C_4,K_n)\ll n^{2-c}$ for the 4-cycle vs clique Ramsey number (Erdős #159) |
OPEN |
0 inv |
3.5 |
1.0 |
36d ago |
|
50ff2c2a |
Determine the digraph Ramsey function $k(n,m)$: independent set vs transitive tournament (Erdős #112) |
OPEN |
0 inv |
3.0 |
3.0 |
36d ago |
|
a8284804 |
Independence number of planar minimum-distance-1 point sets: estimate $g(n)$ and $\lim g(n)/n$ (Erdős #1066) |
OPEN |
0 inv |
3.0 |
3.0 |
36d ago |
|
f862d502 |
Coprime graph of a dense subset of $[n]$: does the extremal threshold force all short odd cycles? (Erdős #883) |
OPEN |
0 inv |
2.0 |
2.5 |
36d ago |
|
75327590 |
Turán density of the complete $r$-graph $K_k^r$ for every fixed $k>r>2$ (Erdős #712) |
OPEN |
0 inv |
4.5 |
2.5 |
36d ago |
|
68a826c5 |
Turán density of the tetrahedron $K_4^3$: evaluate $\lim \mathrm{ex}_3(n,K_4^3)/\binom{n}{3}$ (Erdős #500) |
OPEN |
0 inv |
4.5 |
2.5 |
36d ago |
|
5161b7cf |
Does chromatic number $k$ force the Ramsey number $R(G)$ close to $R(k)$? (Erdős #87) |
OPEN |
0 inv |
2.0 |
2.0 |
36d ago |
|
67078ae2 |
Book size forced in dense graphs covered by triangles: estimate $f_c(n)$, is it $\gg\log n$? (Erdős #80) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
4a822fce |
Constructive exponential lower bound for Ramsey numbers: explicit graphs forcing $R(k)>C^k$ (Erdős #78) |
OPEN |
0 inv |
3.5 |
1.5 |
36d ago |
|
ebb7504d |
Determine the diagonal Ramsey growth constant $\lim_{k\to\infty} R(k)^{1/k}$ (Erdős #77) |
OPEN |
0 inv |
4.5 |
1.0 |
36d ago |
|
fcde6c7d |
Brown–Erdős–Sós conjecture: is the $o(n^2)$ threshold $d_r(e)=(r-2)e+3$? (Erdős #1178) |
OPEN |
0 inv |
4.0 |
2.0 |
36d ago |
|
ca38206a |
The random triangle-removal process: does the surviving edge count $f(n)$ scale as $n^{3/2}$? (Erdős #1155) |
OPEN |
0 inv |
3.0 |
3.0 |
36d ago |
|
86774d3d |
Determine $A_3$, the set of jump densities for $3$-uniform hypergraphs (Erdős–Simonovits) (Erdős #837) |
OPEN |
0 inv |
3.0 |
2.5 |
36d ago |
|
f544b1e3 |
Erdős–Sauer conjecture: decompose every $r$-uniform hypergraph into few cliques and single edges (Erdős #719) |
OPEN |
0 inv |
2.0 |
2.0 |
36d ago |
|
d3e14bd7 |
Extremal edge count forcing two disjoint edge-pairs with equal union in a $t$-uniform hypergraph (Erdős #643) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
45be4a28 |
Does the $3$-uniform hypergraph Ramsey number satisfy $R_3(n)\geq 2^{2^{cn}}$? (Erdős #564) |
OPEN |
0 inv |
4.0 |
1.0 |
36d ago |
|
40e838be |
Sharp $c_\alpha\log n$ asymptotic for the two-colour density-$\alpha$ subgraph threshold (Erdős #563) |
OPEN |
0 inv |
3.0 |
3.0 |
36d ago |
|
9330cf51 |
Hypergraph Ramsey tower height: does $R_r(n)$ grow like a height-$(r-1)$ tower in $n$? (Erdős #562) |
OPEN |
0 inv |
3.5 |
1.0 |
36d ago |
|
87592d1b |
Must large chromatic number with no K_t force two anticomplete c-chromatic subgraphs? (Erdős #1111) |
OPEN |
0 inv |
3.0 |
2.5 |
36d ago |
|
b5105156 |
A minimum-degree threshold on 2^n vertices forcing the n-cube Q_n (Erdős #1035) |
OPEN |
0 inv |
3.0 |
3.0 |
36d ago |
|
6c1038e9 |
Estimate h(n): largest guaranteed triangle degree-sum above the Turán threshold (Erdős #1033) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
cd278e5a |
Estimate f(n,k), the clique partition number for graphs with more than n²/4 edges (Erdős #1017) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
8f2f325f |
Determine h_3(k): fewest vertices in a triangle-free graph of chromatic number k (Erdős #1013) |
OPEN |
0 inv |
3.0 |
2.5 |
36d ago |
|
62208b79 |
Determine f_r(n): fewest edges forcing a triangle in an n-vertex graph of chromatic number ≥ r (Erdős #1011) |
OPEN |
0 inv |
3.0 |
2.5 |
36d ago |
|
7484ed39 |
Estimate h_t(d): fewest edges forcing two edges at distance ≥ t in a max-degree-d graph (Erdős #934) |
OPEN |
0 inv |
3.0 |
3.0 |
36d ago |
|
e36d5e7b |
Estimate f(n): fewest vertices in a tournament where every n vertices have a common dominator (Erdős #902) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
ae16c550 |
Erdős–Hajnal: clique size forced when every 7 vertices span a triangle — estimate $h(n)$ (Erdős #813) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
f4b54a16 |
Erdős–Hajnal: smallest $g(n)$ so every $g(n)$-subset has a $\log n$ clique and $\log n$ independent set (Erdős #805) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
067f65f8 |
Independence number of $K_r$-free graphs: is the AEKS $\frac{\log t}{t}n$ bound true for all $r$? (Erdős #802) |
OPEN |
0 inv |
4.0 |
1.0 |
36d ago |
|
2325b8ed |
Erdős's Alice–Bob clique game on $K_n$: does Bob have a winning strategy for all $n\geq 3$? (Erdős #778) |
OPEN |
0 inv |
3.0 |
3.0 |
36d ago |
|
0e1e781a |
Erdős–Rogers problem: largest triangle-free induced subgraph forced in a $K_4$-free graph (Erdős #620) |
OPEN |
0 inv |
4.0 |
1.5 |
36d ago |
|
d6b3ed12 |
Pin down $t(r)$: transversal number forced by a local $\tau\leq 1$ condition on $r$-uniform hypergraphs (Erdős #616) |
ACTIVE |
3 inv |
3.0 |
2.0 |
15d ago |
|
40f3f739 |
Determine $f(n,k)$: fewest edges forcing degree $\geq k$ in every $(k+2)$-vertex induced subgraph (Erdős #614) |
OPEN |
0 inv |
2.0 |
3.5 |
36d ago |
|
c6a367a7 |
Diameter of $K_{k+1}$-free graphs with minimum degree $d$: is it at most $(3-2/k)n/d$? (Erdős #612) |
OPEN |
0 inv |
3.0 |
2.5 |
36d ago |
|
eb2b00ba |
Sublinear clique transversals under a large-clique hypothesis: is $\tau(G)=o_c(n)$? (Erdős #611) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
54592ee7 |
Edges forcing an $r$-triangle edge: are the thresholds $e(n,r)$ asymptotically flat in $r$? (Erdős #600) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
c6a62326 |
Clique transversal vs. independence: is $\tau(G)\le n-H(n)$ for all graphs? (Erdős #151) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
9d8169b1 |
Strong chromatic index conjecture: is $\mathrm{sq}(G)\le\tfrac54\Delta^2$ for every graph? (Erdős #149) |
OPEN |
0 inv |
4.0 |
2.0 |
36d ago |
|
6907909b |
Turán density of $C_4$ in the hypercube: does $(1/2+o(1))n2^{n-1}$ edges force a $C_4$? (Erdős #86) |
OPEN |
0 inv |
3.0 |
3.5 |
36d ago |
|
c7e81a65 |
Is $f(n)$ — the min-degree threshold forcing a $C_4$ — eventually monotonic? (Erdős #85) |
OPEN |
0 inv |
3.0 |
3.0 |
36d ago |
|
781d464a |
Force a large regular induced subgraph: does $F(n)/\log n\to\infty$? (Erdős #82) |
OPEN |
0 inv |
3.0 |
2.5 |
36d ago |
|
ac3b55c4 |
Partition the edges of a chordal graph into cliques: is $n^2/6+O(n)$ always enough? (Erdős #81) |
OPEN |
0 inv |
3.0 |
3.0 |
36d ago |
|
25026bec |
Common finite-chromatic subgraph of two graphs of chromatic number $\aleph_1$ (Erdős #62) |
OPEN |
0 inv |
3.0 |
1.0 |
36d ago |
|
b83472a9 |
Erdős–Hajnal conjecture: does an excluded induced $H$ force a polynomial clique or independent set? (Erdős #61) |
OPEN |
0 inv |
4.5 |
1.0 |
36d ago |
|
be158ef1 |
Fewest edges of a pancyclic graph: pin down h(n) between log_2 n and log_2 n + log_* n (Erdős #1016) |
OPEN |
0 inv |
3.0 |
3.0 |
36d ago |
|
c5f3e3e0 |
Graphs whose every cycle has more vertices than chords: is the maximum edge count linear? (Erdős #642) |
OPEN |
0 inv |
3.0 |
3.0 |
36d ago |
|
68d35b2c |
Maximum edges in a graph with no two edge-disjoint cycles on the same vertex set (Erdős #585) |
OPEN |
0 inv |
2.5 |
2.5 |
36d ago |
|
7a65bff7 |
Dense subgraphs in which every two edges lie on a short cycle: the Duke–Erdős–Rödl problem (Erdős #584) |
OPEN |
0 inv |
3.0 |
1.0 |
36d ago |
|
7ebfa71d |
Erdős–Gallai conjecture: decompose any n-vertex graph into O(n) edge-disjoint cycles and edges (Erdős #184) |
OPEN |
0 inv |
4.0 |
1.0 |
36d ago |
|
3e5a3bae |
How many cycle sets are achievable on $n$ vertices? Prove $f(n)/2^{n/2}\to\infty$ (Erdős #84) |
OPEN |
0 inv |
3.0 |
2.5 |
36d ago |
|
d05d68b4 |
Is the sum of reciprocals of cycle lengths minimised by complete bipartite graphs? (Erdős #65) |
OPEN |
0 inv |
3.0 |
3.0 |
36d ago |
|
1c5ffd8b |
Beyond the $C_4$ extremal number: must a graph contain $\gg n^{1/2}$ four-cycles? (Erdős #60) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
76ff73a2 |
Prove the two-sided density-Ramsey function of $K_n$ satisfies $F(n,\alpha)\sim c_\alpha \log n$ (Erdős #162) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
85d2c20f |
Jumps of the density-Ramsey function $F^{(t)}(n,\alpha)$: does everything happen at $\alpha=0$? (Erdős #161) |
OPEN |
0 inv |
3.5 |
1.0 |
36d ago |
|
69db6e3b |
Does large chromatic number force triangle-free subgraphs of chromatic number $\kappa$? (Erdős #1175) |
OPEN |
0 inv |
2.5 |
1.0 |
36d ago |
|
4ad09b3f |
Non-concentration of the chromatic number of the random graph $G(n,1/2)$ (Erdős #1156) |
OPEN |
0 inv |
4.0 |
1.0 |
36d ago |
|
4f5c1c29 |
Maximum chromatic number of triangle-free graphs: close the factor-2 gap for $f(n)$ (Erdős #1104) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
3d5984ac |
Must a graph of chromatic number $\aleph_1$ contain an infinitely-connected countable subgraph? (Erdős #1068) |
OPEN |
0 inv |
3.0 |
1.0 |
36d ago |
|
358ba005 |
Intersecting $r$-uniform hypergraphs of chromatic number 3: must two edges share $\gg r$ vertices? (Erdős #836) |
OPEN |
0 inv |
3.0 |
2.5 |
36d ago |
|
3c59421f |
Making $n$-vertex subgraphs bipartite: is $h_G(n)/n\to\infty$ when $\chi(G)=\aleph_1$? (Erdős #111) |
OPEN |
0 inv |
2.5 |
1.0 |
36d ago |
|
51b203c3 |
4-chromatic edge-critical graphs with linear minimum degree: do they exist? (Erdős #1032) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
a4945b3d |
k-vertex-critical graphs in which every critical edge set is large: the last open case k=4 (Erdős #944) |
OPEN |
0 inv |
3.0 |
3.5 |
36d ago |
|
7b50b1dd |
Maximum chromatic number of $K_k$-free graphs: is $f_k(n)\gg n^{1-1/(k-1)}$ up to logs? (Erdős #920) |
OPEN |
0 inv |
3.0 |
1.0 |
36d ago |
|
f57f01a5 |
Order type $\omega_2^2$, chromatic number $\aleph_2$, lesser-type subgraphs countably chromatic? (Erdős #919) |
OPEN |
0 inv |
2.0 |
1.0 |
36d ago |
|
41f78888 |
A graph of chromatic number $\aleph_2$ whose $\aleph_1$-vertex subgraphs are countably chromatic (Erdős #918) |
OPEN |
0 inv |
3.0 |
1.0 |
36d ago |
|
23c74681 |
Maximum edges of a k-chromatic critical graph: is $f_6(n)\sim n^2/4$? (Erdős #917) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
50cca059 |
Does large chromatic or cochromatic number force large dichromatic number? (Erdős #761) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
7abf1963 |
Subgraphs of the same infinite chromatic number avoiding short odd cycles (Erdős #740) |
OPEN |
0 inv |
3.0 |
1.0 |
36d ago |
|
3d9b5f5d |
Must a triangle-free graph of infinite chromatic number induce every tree? (Erdős #738) |
OPEN |
0 inv |
3.0 |
1.0 |
36d ago |
|
ca36ef09 |
Chromatic number of r-distance graphs in the plane: is L(r) polynomial in r? (Erdős #706) |
OPEN |
0 inv |
3.0 |
3.5 |
36d ago |
|
e14bbdc3 |
Does huge chromatic number force an odd cycle spanning a subgraph of chromatic number k? (Erdős #640) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
02a47de8 |
Determine n(k): the fewest vertices in a bipartite graph with list chromatic number exceeding k (Erdős #629) |
OPEN |
0 inv |
3.0 |
3.0 |
36d ago |
|
ad23ee58 |
Does f(n)(log_2 n)^2/n converge, for f(n) the maximum chromatic-to-clique ratio on n vertices? (Erdős #627) |
OPEN |
0 inv |
3.0 |
1.0 |
36d ago |
|
cc16d0bd |
Integer-distance graphs in general position: can the chromatic number be infinite? (Erdős #130) |
OPEN |
0 inv |
3.0 |
2.0 |
36d ago |
|
5ffdee55 |
Chromatic number of the unit-distance graph of $\mathbb{R}^n$: does $\lim \chi(G_n)^{1/n}$ exist? (Erdős #704) |
OPEN |
0 inv |
4.0 |
2.0 |
36d ago |
|
bb3af74d |
Girth versus chromatic number: do $g_k(n)/\log n$ and $\log h^{(m)}(n)/\log n$ have limits? (Erdős #626) |
OPEN |
0 inv |
3.0 |
1.5 |
36d ago |
|
1979d890 |
Does large chromatic number force a subgraph of girth $\ge r$ and chromatic number $\ge k$? (Erdős #108) |
OPEN |
0 inv |
3.5 |
1.0 |
36d ago |
|
9f35d3df |
An $\aleph_1$-chromatic graph on $\aleph_1$ vertices whose finite subgraphs are nearly independent (Erdős #75) |
OPEN |
0 inv |
3.0 |
1.0 |
36d ago |
|
a0fd3bd7 |
An infinite-chromatic graph whose $n$-vertex subgraphs are within $f(n)$ edges of bipartite (Erdős #74) |
OPEN |
0 inv |
3.0 |
1.0 |
36d ago |
|
15a43cd1 |
Do $n/2$ vertices of degree $\geq n/2$ force every tree on $\leq n/2$ vertices? (Erdős #580) |
OPEN |
1 inv |
3.0 |
2.5 |
37d ago |
|
822be9d3 |
Colour k-subsets of [2k] with k+1 colours so every (k+1)-set is rainbow: possible for k>2? (Erdős #835) |
OPEN |
0 inv |
2.0 |
3.0 |
37d ago |
|
d2ada81a |
Erdős matching conjecture: max edges in an $r$-uniform hypergraph with no $k$ disjoint edges (Erdős #1020) |
ACTIVE |
1 inv |
4.0 |
3.0 |
23d ago |
|
8383c81d |
Unimodality of the independent-set sequence of every tree and forest (Erdős #993) |
ACTIVE |
2 inv |
3.0 |
3.0 |
23d ago |
|
4694be38 |
Tree packing conjecture: do trees $T_2,\ldots,T_n$ with $|T_k|=k$ decompose $K_n$? (Erdős #743) |
ACTIVE |
1 inv |
4.0 |
3.0 |
23d ago |
|
c612c9e6 |
Balanced $r$-colourings of $K_{r^2+1}$: must some $K_{r+1}$ miss a colour? (Erdős #617) |
OPEN |
0 inv |
3.0 |
3.0 |
37d ago |
|
6230b286 |
Erdős–Sós conjecture: (k-1)n/2 + 1 edges force every tree on k+1 vertices (Erdős #548) |
OPEN |
0 inv |
4.0 |
2.0 |
37d ago |
|
2e762fb0 |
Tuza's conjecture: delete 2k edges to kill all triangles when only k are edge-disjoint (Erdős #167) |
OPEN |
0 inv |
3.0 |
3.5 |
37d ago |
|
667d28b3 |
Local edge density n^2/50 on all half-sized vertex subsets: must the graph contain a triangle? (Erdős #128) |
OPEN |
0 inv |
3.0 |
2.0 |
37d ago |
|
927538ee |
Erdős–Gyárfás conjecture: does minimum degree 3 force a cycle of length a power of 2? (Erdős #64) |
OPEN |
0 inv |
4.0 |
3.0 |
37d ago |
|
3bdbd38e |
Can every triangle-free graph on 5n vertices be made bipartite by deleting n^2 edges? (Erdős #23) |
OPEN |
0 inv |
3.0 |
2.5 |
37d ago |
|
2c05a836 |
Erdős–Lovász Tihany conjecture: disjoint subgraphs with $\chi\ge a$ and $\chi\ge b$ when $a+b=\chi+1$ (Erdős #628) |
OPEN |
0 inv |
4.0 |
2.5 |
37d ago |
|
ebe72af7 |
Formalize the Graceful Tree (Ringel–Kotzig) conjecture in Lean 4 |
OPEN |
0 inv |
4.0 |
1.0 |
45d ago |
|
facb9007 |
Do any three longest paths in a connected graph share a common vertex? |
OPEN |
0 inv |
3.0 |
3.0 |
45d ago |
|
83ebe9db |
Acyclic Edge Coloring Conjecture: does every graph have an acyclic edge coloring with Δ + 2 colors? |
OPEN |
0 inv |
3.0 |
4.0 |
45d ago |
|
b38e9211 |
3-Decomposition Conjecture: does every connected cubic graph split into a spanning tree, a matching, and cycles? |
OPEN |
0 inv |
3.0 |
4.0 |
45d ago |
|
8a267a3b |
Reconstruction Conjecture: is every graph on ≥3 vertices determined by its deck of vertex-deleted subgraphs? |
OPEN |
0 inv |
4.0 |
2.0 |
45d ago |
|
8949994e |
Van Dam–Haemers Conjecture: are almost all graphs determined by their adjacency spectrum? |
OPEN |
0 inv |
4.0 |
3.0 |
45d ago |
|
5a7b263a |
Jørgensen's Conjecture: is every 6-connected graph with no K_6 minor apex? |
OPEN |
0 inv |
4.0 |
3.0 |
45d ago |
|
96c35e88 |
Total Coloring Conjecture: is the total chromatic number of every graph at most Δ + 2? |
OPEN |
0 inv |
4.0 |
3.0 |
45d ago |
|
f75dd724 |
Borodin–Kostochka Conjecture: for Δ ≥ 9, does no K_Δ force χ ≤ Δ − 1? |
OPEN |
0 inv |
4.0 |
2.0 |
45d ago |
|
b6b9fcf5 |
Is the star chromatic index of every subcubic graph at most 6? |
OPEN |
0 inv |
3.0 |
4.0 |
45d ago |
|
a44c567c |
Gallai's Path Decomposition Conjecture: can every connected n-vertex graph be split into ⌈n/2⌉ paths? |
OPEN |
0 inv |
4.0 |
3.0 |
45d ago |
|
96f0741c |
Cycle Double Cover Conjecture: does every bridgeless graph have cycles covering each edge exactly twice? |
OPEN |
0 inv |
5.0 |
2.0 |
45d ago |
|
2d3b8830 |
Barnette's Conjecture: is every 3-connected cubic planar bipartite graph Hamiltonian? |
OPEN |
0 inv |
4.0 |
3.0 |
45d ago |