Erdős · problems
OEIS index →← the campaignThe Erdős problems.
271 of 1217 · 34 sealed
#23Can every triangle-free graph on $5n$ vertices be made bipartite by deleting at most $n^2$ edges?graph theory · 1 Vela attempt (extends prior work) · AI tried (unverified) · A389646#993The independent set sequence of any tree or forest is unimodal.In other words, if $i_k(G)$ counts the number of independent sets of vertices of size $k$ in a graph $G$, and $T$ is any tree or forest, …graph theory · 1 Vela attempt (extends prior work) · AI tried (unverified) · possible#85Let $n\geq 4$ and $f(n)$ be minimal such that every graph on $n$ vertices with minimal degree $\geq f(n)$ contains a $C_4$. Is it true that, for all large $n$, $f(n+1)\geq f(n)$?graph theory · 1 Vela attempt (honest null) · AI tried (unverified) · A006672,possible#108For every $r\geq 4$ and $k\geq 2$ is there some finite $f(k,r)$ such that every graph of chromatic number $\geq f(k,r)$ contains a subgraph of girth $\geq r$ and chromatic number $\geq k$?graph theory · 1 Vela attempt (honest null) · AI tried (unverified) · possible#184Any graph on $n$ vertices can be decomposed into $O(n)$ many edge-disjoint cycles and edges.graph theory · 1 Vela attempt (honest null) · AI tried (unverified) · possible#567Let $G$ be either $Q_3$ or $K_{3,3}$ or $H_5$ (the last formed by adding two vertex-disjoint chords to $C_5$). Is it true that, if $H$ has $m$ edges and no isolated vertices, then\[R(G,H)\ll m?\]graph theory · 1 Vela attempt (honest null) · AI tried (unverified) · N/A#595Is there an infinite graph $G$ which contains no $K_4$ and is not the union of countably many triangle-free graphs?graph theory · 1 Vela attempt (honest null) · AI tried (unverified) · N/A#740Let $\mathfrak{m}$ be an infinite cardinal and $G$ be a graph with chromatic number $\mathfrak{m}$. Let $r\geq 1$. Must $G$ contain a subgraph of chromatic number $\mathfrak{m}$ which does not contain…graph theory · 1 Vela attempt (honest null) · AI tried (unverified) · N/A#1020Let $f(n;r,k)$ be the maximal number of edges in an $r$-uniform hypergraph which contains no set of $k$ many independent edges. For all $r\geq 3$,\[f(n;r,k)=\max\left(\binom{rk-1}{r}, \binom{n}{r}-\bi…Erdős matching conjecture · graph theory · AI refuted · N/A#61For any graph $H$ is there some $c=c(H)>0$ such that every graph $G$ on $n$ vertices that does not contain $H$ as an induced subgraph contains either a complete graph or independent set on $\geq n…graph theory · AI tried (unverified) · N/A#64Does every finite graph with minimum degree at least 3 contain a cycle of length $2^k$ for some $k\geq 2$?graph theory · AI tried (unverified) · N/A#74Let $f(n)\to \infty$ (possibly very slowly). Is there a graph of infinite chromatic number such that every finite subgraph on $n$ vertices can be made bipartite by deleting at most $f(n)$ edges?graph theory · AI tried (unverified) · N/A#75Is there a graph of chromatic number $\aleph_1$ with $\aleph_1$ vertices such that for all $\epsilon>0$ if $n$ is sufficiently large and $H$ is a subgraph on $n$ vertices then $H$ contains an inde…graph theory · AI tried (unverified) · N/A#82Let $F(n)$ be maximal such that every graph on $n$ vertices contains a regular induced subgraph on at least $F(n)$ vertices. Prove that $F(n)/\log n\to \infty$.graph theory · AI tried (unverified) · A120414,A390256,A390257,A390919,A392636,A394400,A394462,A394539,A394563,A394564,A394573,A394574,A394930,A394933#128Let $G$ be a graph with $n$ vertices such that every induced subgraph on $\geq \lfloor n/2\rfloor$ vertices has more than $n^2/50$ edges. Must $G$ contain a triangle?graph theory · AI tried (unverified) · N/A#562Let $R_r(n)$ denote the $r$-uniform hypergraph Ramsey number: the minimal $m$ such that if we $2$-colour all edges of the complete $r$-uniform hypergraph on $m$ vertices then there must be some monoch…graph theory · AI tried (unverified) · possible#564Let $R_3(n)$ be the minimal $m$ such that if the edges of the $3$-uniform hypergraph on $m$ vertices are $2$-coloured then there is a monochromatic copy of the complete $3$-uniform hypergraph on $n$ v…graph theory · AI tried (unverified) · possible#566Let $G$ be such that any subgraph on $k$ vertices has at most $2k-3$ edges. Is it true that, if $H$ has $m$ edges and no isolated vertices, then\[R(G,H)\ll m?\]graph theory · AI tried (unverified) · N/A#596For which graphs $G_1,G_2$ is it true that for every $n\geq 1$ there is a graph $H$ without a $G_1$ but if the edges of $H$ are $n$-coloured then there is a monochromatic copy of $G_2$, and yet for ev…graph theory · AI tried (unverified) · N/A#617Let $r\geq 3$. If the edges of $K_{r^2+1}$ are $r$-coloured then there exist $r+1$ vertices with at least one colour missing on the edges of the induced $K_{r+1}$.graph theory · AI tried (unverified) · N/A#705Let $G$ be a finite unit distance graph in $\mathbb{R}^2$ (i.e. the vertices are a finite collection of points in $\mathbb{R}^2$ and there is an edge between two points if and only if the distance bet…graph theory · solved · AI tried (unverified) · N/A#750Let $f(m)$ be some function such that $f(m)\to \infty$ as $m\to \infty$. Does there exist a graph $G$ of infinite chromatic number such that every subgraph on $m$ vertices contains an independent set …graph theory · AI tried (unverified) · N/A#812Is it true that\[\frac{R(n+1)}{R(n)}\geq 1+c\]for some constant $c>0$, for all large $n$? Is it true that\[R(n+1)-R(n) \gg n^2?\]graph theory · AI tried (unverified) · A059442#835Does there exist a $k>2$ such that the $k$-sized subsets of $\{1,\ldots,2k\}$ can be coloured with $k+1$ colours such that for every $A\subset \{1,\ldots,2k\}$ with $\lvert A\rvert=k+1$ all $k+1$ …graph theory · AI tried (unverified) · N/A#918Is there a graph with $\aleph_2$ vertices and chromatic number $\aleph_2$ such that every subgraph on $\aleph_1$ vertices has chromatic number $\leq\aleph_0$?Is there a graph with $\aleph_{\omega+1}$ …graph theory · AI tried (unverified) · N/A#920Let $f_k(n)$ be the maximum possible chromatic number of a graph with $n$ vertices which contains no $K_k$.Is it true that, for $k\geq 4$,\[f_k(n) \gg \frac{n^{1-\frac{1}{k-1}}}{(\log n)^{c_k}}\]for s…graph theory · AI tried (unverified) · possible#944A critical vertex, edge, or set of edges, is one whose deletion lowers the chromatic number.Let $k\geq 4$ and $r\geq 1$. Must there exist a graph $G$ with chromatic number $k$ such that every vertex i…graph theory · AI tried (unverified) · N/A#1068Does every graph with chromatic number $\aleph_1$ contain a countable subgraph which is infinitely vertex-connected?graph theory · AI tried (unverified) · N/A#1104Let $f(n)$ be the maximum possible chromatic number of a triangle-free graph on $n$ vertices. Estimate $f(n)$.graph theory · AI tried (unverified) · A292528#1105The anti-Ramsey number $\mathrm{AR}(n,G)$ is the maximum possible number of colours in which the edges of $K_n$ can be coloured without creating a rainbow copy of $G$ (i.e. one in which all edges have…graph theory · solved · AI tried (unverified) · possible#60Does every graph on $n$ vertices with $>\mathrm{ex}(n;C_4)$ edges contain $\gg n^{1/2}$ many copies of $C_4$?graph theory · AI tried (unverified) · A006855#62If $G_1,G_2$ are two graphs with chromatic number $\aleph_1$ then must there exist a graph $G$ whose chromatic number is $4$ (or even $\aleph_0$) which is a subgraph of both $G_1$ and $G_2$?graph theory · AI tried (unverified) · N/A#65Let $G$ be a graph with $n$ vertices and $kn$ edges, and $a_1<a_2<\cdots $ be the lengths of cycles in $G$. Is it true that\[\sum\frac{1}{a_i}\gg \log k?\]Is the sum $\sum\frac{1}{a_i}$ minimi…graph theory · AI tried (unverified) · N/A#70Let $\mathfrak{c}$ be the ordinal of the real numbers, $\beta$ be any countable ordinal, and $2\leq n<\omega$. Is it true that $\mathfrak{c}\to (\beta, n)_2^3$?graph theory · AI tried (unverified) · N/A#77If $R(k)$ is the Ramsey number for $K_k$, the minimal $n$ such that every $2$-colouring of the edges of $K_n$ contains a monochromatic copy of $K_k$, then find the value of\[\lim_{k\to \infty}R(k)^{1/…graph theory · AI tried (unverified) · A059442#78Let $R(k)$ be the Ramsey number for $K_k$, the minimal $n$ such that every $2$-colouring of the edges of $K_n$ contains a monochromatic copy of $K_k$.Give a constructive proof that $R(k)>C^k$ for …graph theory · AI tried (unverified) · A059442#80Let $c>0$ and let $f_c(n)$ be the maximal $m$ such that every graph $G$ with $n$ vertices and at least $cn^2$ edges, where each edge is contained in at least one triangle, must contain a book of s…graph theory · AI tried (unverified) · N/A#81Let $G$ be a chordal graph on $n$ vertices - that is, $G$ has no induced cycles of length greater than $3$. Can the edges of $G$ be partitioned into $n^2/6+O(n)$ many cliques?graph theory · AI tried (unverified) · possible#84The cycle set of a graph $G$ on $n$ vertices is a set $A\subseteq \{3,\ldots,n\}$ such that there is a cycle in $G$ of length $\ell$ if and only if $\ell \in A$. Let $f(n)$ count the number of possibl…graph theory · AI tried (unverified) · possible#86Let $Q_n$ be the $n$-dimensional hypercube graph (so that $Q_n$ has $2^n$ vertices and $n2^{n-1}$ edges). Is it true that every subgraph of $Q_n$ with\[\geq \left(\frac{1}{2}+o(1)\right)n2^{n-1}\]many…graph theory · AI tried (unverified) · A245762#87Let $\epsilon >0$. Is it true that, if $k$ is sufficiently large, then\[R(G)>(1-\epsilon)^kR(k)\]for every graph $G$ with chromatic number $\chi(G)=k$? Even stronger, is there some $c>0$ s…graph theory · AI tried (unverified) · A059442,possible#111If $G$ is a graph let $h_G(n)$ be defined such that any subgraph of $G$ on $n$ vertices can be made bipartite after deleting at most $h_G(n)$ edges. What is the behaviour of $h_G(n)$? Is it true that …graph theory · AI tried (unverified) · N/A#112Let $k=k(n,m)$ be minimal such that any directed graph on $k$ vertices must contain either an independent set of size $n$ or a transitive tournament of size $m$. Determine $k(n,m)$.graph theory · AI tried (unverified) · possible#129Let $R(n;k,r)$ be the smallest $N$ such that if the edges of $K_N$ are $r$-coloured then there is a set of $n$ vertices which does not contain a copy of $K_k$ in at least one of the $r$ colours. Prove…ambiguous statement · graph theory · AI tried (unverified) · possible#130Let $A\subset\mathbb{R}^2$ be an infinite set which contains no three points on a line and no four points on a circle. Consider the graph with vertices the points in $A$, where two vertices are joined…graph theory · AI tried (unverified) · N/A#146If $H$ is bipartite and is $r$-degenerate, that is, every induced subgraph of $H$ has minimum degree $\leq r$, then\[\mathrm{ex}(n;H) \ll n^{2-1/r}.\]graph theory · AI tried (unverified) · N/A#149The strong chromatic index of a graph $G$, denoted by $\mathrm{sq}(G)$, is the minimum $k$ such that the edges of $G$ can be partitioned into $k$ sets of 'strongly independent' edges, that is, such th…graph theory · AI tried (unverified) · N/A#151For a graph $G$ let $\tau(G)$ denote the minimal number of vertices that include at least one from each maximal clique of $G$ on at least two vertices (sometimes called the clique transversal number).…graph theory · AI tried (unverified) · possible#159There exists some constant $c>0$ such that$$R(C_4,K_n) \ll n^{2-c}.$$graph theory · AI tried (unverified) · possible#165Give an asymptotic formula for $R(3,k)$.graph theory · AI tried (unverified) · A000791#167If $G$ is a graph with at most $k$ edge disjoint triangles then can $G$ be made triangle-free after removing at most $2k$ edges?graph theory · AI tried (unverified) · N/A#180If $\mathcal{F}$ is a finite set of finite graphs then $\mathrm{ex}(n;\mathcal{F})$ is the maximum number of edges a graph on $n$ vertices can have without containing any subgraphs from $\mathcal{F}$.…graph theory · AI tried (unverified) · N/A#181Let $Q_n$ be the $n$-dimensional hypercube graph (so that $Q_n$ has $2^n$ vertices and $n2^{n-1}$ edges). Prove that\[R(Q_n) \ll 2^n.\]graph theory · AI tried (unverified) · possible#183Let $R(3;k)$ be the minimal $n$ such that if the edges of $K_n$ are coloured with $k$ colours then there must exist a monochromatic triangle. Determine\[\lim_{k\to \infty}R(3;k)^{1/k}.\]graph theory · AI tried (unverified) · A003323#500What is $\mathrm{ex}_3(n,K_4^3)$? That is, the largest number of $3$-edges which can placed on $n$ vertices so that there exists no $K_4^3$, a set of 4 vertices which is covered by all 4 possible $3$-…graph theory · AI tried (unverified) · A140462#533Let $\delta>0$. If $n$ is sufficiently large and $G$ is a graph on $n$ vertices with no $K_5$ and at least $\delta n^2$ edges then $G$ contains a set of $\gg_\delta n$ vertices containing no trian…graph theory · solved · AI tried (unverified) · N/A#544Show that\[R(3,k+1)-R(3,k)\to\infty\]as $k\to \infty$. Similarly, prove or disprove that\[R(3,k+1)-R(3,k)=o(k).\]graph theory · AI tried (unverified) · A000791#545Let $G$ be a graph with $m$ edges and no isolated vertices. Is the Ramsey number $R(G)$ maximised when $G$ is 'as complete as possible'? That is, if $m=\binom{n}{2}+t$ edges with $0\leq t<n$ then …graph theory · AI tried (unverified) · A059442,possible#548Let $n\geq k+1$. Every graph on $n$ vertices with at least $\frac{k-1}{2}n+1$ edges contains every tree on $k+1$ vertices.graph theory · AI tried (unverified) · N/A#550Let $m_1\leq\cdots\leq m_k$ and $n$ be sufficiently large. If $T$ is a tree on $n$ vertices and $G$ is the complete multipartite graph with vertex class sizes $m_1,\ldots,m_k$ then prove that\[R(T,G)\…graph theory · AI tried (unverified) · N/A#552Determine the Ramsey number\[R(C_4,S_n),\]where $S_n=K_{1,n}$ is the star on $n+1$ vertices.In particular, is it true that, for any $c>0$, there are infinitely many $n$ such that\[R(C_4,S_n)\leq n…graph theory · AI tried (unverified) · A006672#554Let $R_k(G)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Show that\[\lim_{k\to \infty}\frac{R_k(C_{2n+1})}{R_k(K_3)}=0\]for any $…graph theory · AI tried (unverified) · possible#555Let $R_k(G)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Determine the value of\[R_k(C_{2n}).\]graph theory · AI tried (unverified) · A389313,possible#557Let $R_k(G)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Is it true that\[R_k(T)\leq kn+O(1)\]for any tree $T$ on $n$ vertices?graph theory · AI tried (unverified) · N/A#558Let $R_k(G)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Determine\[R_k(K_{s,t})\]where $K_{s,t}$ is the complete bipartite graph…graph theory · AI tried (unverified) · possible#560Let $\hat{R}(G)$ denote the size Ramsey number, the minimal number of edges $m$ such that there is a graph $H$ with $m$ edges such that in any $2$-colouring of the edges of $H$ there is a monochromati…graph theory · AI tried (unverified) · possible#561Let $\hat{R}(G)$ denote the size Ramsey number, the minimal number of edges $m$ such that there is a graph $H$ with $m$ edges such that in any $2$-colouring of the edges of $H$ there is a monochromati…graph theory · AI tried (unverified) · N/A#563Let $F(n,\alpha)$ denote the smallest $m$ such that there exists a $2$-colouring of the edges of $K_n$ so that every $X\subseteq [n]$ with $\lvert X\rvert\geq m$ contains more than $\alpha \binom{\lve…graph theory · AI tried (unverified) · N/A#568Let $G$ be a graph such that $R(G,T_n)\ll n$ for any tree $T_n$ on $n$ vertices and $R(G,K_n)\ll n^2$. Is it true that, for any $H$ with $m$ edges and no isolated vertices,\[R(G,H)\ll m?\]graph theory · AI tried (unverified) · N/A#569Let $k\geq 1$. What is the best possible $c_k$ such that\[R(C_{2k+1},H)\leq c_k m\]for any graph $H$ on $m$ edges without isolated vertices?graph theory · AI tried (unverified) · N/A#570Let $k\geq 3$. Is it true that, if $m$ is sufficiently large, for any graph $H$ on $m$ edges without isolated vertices,\[R(C_k,H) \leq 2m+\left\lfloor\frac{k-1}{2}\right\rfloor?\]graph theory · solved · AI tried (unverified) · N/A#571Show that for any rational $\alpha \in [1,2)$ there exists a bipartite graph $G$ such that\[\mathrm{ex}(n;G)\asymp n^{\alpha}.\]graph theory · AI tried (unverified) · N/A#572Show that for $k\geq 3$\[\mathrm{ex}(n;C_{2k})\gg n^{1+\frac{1}{k}}.\]graph theory · AI tried (unverified) · possible#573Is it true that\[\mathrm{ex}(n;\{C_3,C_4\})\sim (n/2)^{3/2}?\]graph theory · AI tried (unverified) · A006856#574Is it true that, for $k\geq 2$,\[\mathrm{ex}(n;\{C_{2k-1},C_{2k}\})=(1+o(1))(n/2)^{1+\frac{1}{k}}.\]graph theory · solved · AI tried (unverified) · possible#575If $\mathcal{F}$ is a finite set of finite graphs then $\mathrm{ex}(n;\mathcal{F})$ is the maximum number of edges a graph on $n$ vertices can have without containing any subgraphs from $\mathcal{F}$.…graph theory · AI tried (unverified) · N/A#576Let $Q_k$ be the $k$-dimensional hypercube graph (so that $Q_k$ has $2^k$ vertices and $k2^{k-1}$ edges). Determine the behaviour of\[\mathrm{ex}(n;Q_k).\]graph theory · AI tried (unverified) · possible#579Let $\delta>0$. If $n$ is sufficiently large and $G$ is a graph on $n$ vertices with no $K_{2,2,2}$ and at least $\delta n^2$ edges then $G$ contains an independent set of size $\gg_\delta n$.graph theory · AI tried (unverified) · N/A#583Every connected graph on $n$ vertices can be partitioned into at most $\lceil n/2\rceil$ edge-disjoint paths.graph theory · AI tried (unverified) · N/A#584Let $G$ be a graph with $n$ vertices and $\delta n^{2}$ edges. Are there subgraphs $H_1,H_2\subseteq G$ such that $H_1$ has $\gg \delta^3n^2$ edges and every two edges in $H_1$ are contained in a cycl…graph theory · AI tried (unverified) · N/A#585What is the maximum number of edges that a graph on $n$ vertices can have if it does not contain two edge-disjoint cycles with the same vertex set?graph theory · AI tried (unverified) · possible#597Let $G$ be a graph on at most $\aleph_1$ vertices which contains no $K_4$ and no $K_{\aleph_0,\aleph_0}$ (the complete bipartite graph with $\aleph_0$ vertices in each class). Is it true that\[\omega_…graph theory · AI tried (unverified) · N/A#600Let $e(n,r)$ be minimal such that every graph on $n$ vertices with at least $e(n,r)$ edges, each edge contained in at least one triangle, must have an edge contained in at least $r$ triangles. Let $r\…graph theory · AI tried (unverified) · possible#601For which limit ordinals $\alpha$ is it true that if $G$ is a graph with vertex set $\alpha$ then $G$ must have either an infinite path or independent set on a set of vertices with order type $\alpha$…graph theory · AI tried (unverified) · N/A#609Let $f(n)$ be the minimal $m$ such that if the edges of $K_{2^n+1}$ are coloured with $n$ colours then there must be a monochromatic odd cycle of length at most $m$. Estimate $f(n)$.graph theory · AI tried (unverified) · possible#610For a graph $G$ let $\tau(G)$ denote the minimal number of vertices that include at least one from each maximal clique of $G$ (aside from isolated vertices). This is sometimes called the clique transv…graph theory · solved · AI tried (unverified) · possible#611For a graph $G$ let $\tau(G)$ denote the minimal number of vertices that include at least one from each maximal clique of $G$ (sometimes called the clique transversal number).Is it true that if all ma…graph theory · AI tried (unverified) · N/A#612Let $G$ be a connected graph with $n$ vertices, minimum degree $d$, and diameter $D$. Show if that $G$ contains no $K_{2r}$ and $(r-1)(3r+2)\mid d$ then\[D\leq \frac{2(r-1)(3r+2)}{2r^2-1}\frac{n}{d}+O…graph theory · AI tried (unverified) · N/A#614Let $f(n,k)$ be minimal such that there is a graph with $n$ vertices and $f(n,k)$ edges where every set of $k+2$ vertices induces a subgraph with maximum degree at least $k$. Determine $f(n,k)$.graph theory · AI tried (unverified) · possible#616Let $r\geq 3$. For an $r$-uniform hypergraph $G$ let $\tau(G)$ denote the covering number (or transversal number), the minimum size of a set of vertices which includes at least one from each edge in $…graph theory · AI tried (unverified) · N/A#619For a triangle-free graph $G$ let $h_r(G)$ be the smallest number of edges that need to be added to $G$ so that it has diameter $r$ (while preserving the property of being triangle-free).Is it true th…graph theory · AI tried (unverified) · N/A#620If $G$ is a graph on $n$ vertices without a $K_4$ then how large a triangle-free induced subgraph must $G$ contain?Erdős-Rogers problem · graph theory · AI tried (unverified) · possible#625The cochromatic number of $G$, denoted by $\zeta(G)$, is the minimum number of colours needed to colour the vertices of $G$ such that each colour class induces either a complete graph or empty graph. …graph theory · AI tried (unverified) · N/A#626Let $k\geq 4$ and $g_k(n)$ denote the largest $m$ such that there is a graph on $n$ vertices with chromatic number $k$ and girth $>m$ (i.e. contains no cycle of length $\leq m$). Does\[\lim_{n\to …graph theory · AI tried (unverified) · possible#627Let $\omega(G)$ denote the clique number of $G$ and $\chi(G)$ the chromatic number. If $f(n)$ is the maximum value of $\chi(G)/\omega(G)$, as $G$ ranges over all graphs on $n$ vertices, then does\[\li…graph theory · AI tried (unverified) · possible#628Let $G$ be a graph with chromatic number $k$ containing no $K_k$. If $a,b\geq 2$ and $a+b=k+1$ then must there exist two disjoint subgraphs of $G$ with chromatic numbers $\geq a$ and $\geq b$ respecti…Erdős-Lovász Tihany Conjecture · graph theory · AI tried (unverified) · N/A#629The list chromatic number $\chi_L(G)$ is defined to be the minimal $k$ such that for any assignment of a list of $k$ colours to each vertex of $G$ (perhaps different lists for different vertices) a co…graph theory · AI tried (unverified) · possible#638Let $S$ be a family of finite graphs such that for every $n$ there is some $G_n\in S$ such that if the edges of $G_n$ are coloured with $n$ colours then there is a monochromatic triangle.Is it true th…graph theory · AI tried (unverified) · N/A#640Let $k\geq 3$. Does there exist some $f(k)$ such that if a graph $G$ has chromatic number $\geq f(k)$ then $G$ must contain some odd cycle whose vertices span a graph of chromatic number $\geq k$?graph theory · AI tried (unverified) · N/A#642Let $f(n)$ be the maximal number of edges in a graph on $n$ vertices such that all cycles have more vertices than chords. Is it true that $f(n)\ll n$?graph theory · AI tried (unverified) · possible#643Let $f(n;t)$ be minimal such that if a $t$-uniform hypergraph on $n$ vertices contains at least $f(n;t)$ edges then there must be four edges $A,B,C,D$ such that\[A\cup B= C\cup D\]and\[A\cap B=C\cap D…graph theory · AI tried (unverified) · possible#667Let $p,q\geq 1$ be fixed integers. We define $H(n)=H(N;p,q)$ to be the largest $m$ such that any graph on $n$ vertices where every set of $p$ vertices spans at least $q$ edges must contain a complete …graph theory · AI tried (unverified) · N/A#704Let $G_n$ be the unit distance graph in $\mathbb{R}^n$, with two vertices joined by an edge if and only if the distance between them is $1$.Estimate the chromatic number $\chi(G_n)$. Does it grow expo…graph theory · AI tried (unverified) · N/A#706Let $L(r)$ be such that if $G$ is a graph formed by taking a finite set of points $P$ in $\mathbb{R}^2$ and some set $A\subset (0,\infty)$ of size $r$, where the vertex set is $P$ and there is an edge…graph theory · AI tried (unverified) · possible#712Determine, for any $k>r>2$, the value of\[\frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}},\]where $\mathrm{ex}_r(n,K_k^r)$ is the largest number of $r$-edges which can placed on $n$ vertices so th…graph theory · AI tried (unverified) · possible#713Is it true that, for every bipartite graph $G$, there exists some $\alpha\in [1,2)$ and $c>0$ such that\[\mathrm{ex}(n;G)\sim cn^\alpha?\]Must $\alpha$ be rational?graph theory · AI tried (unverified) · N/A#714Is it true that\[\mathrm{ex}(n; K_{r,r}) \gg n^{2-1/r}?\]graph theory · AI tried (unverified) · possible#719Let $\mathrm{ex}_r(n;K_{r+1}^r)$ be the maximum number of $r$-edges that can be placed on $n$ vertices without forming a $K_{r+1}^r$ (the $r$-uniform complete graph on $r+1$ vertices).Is every $r$-hyp…graph theory · AI tried (unverified) · possible#738If $G$ has infinite chromatic number and is triangle-free (contains no $K_3$) then must $G$ contain every tree as an induced subgraph?graph theory · AI tried (unverified) · N/A#743Let $T_2,\ldots,T_n$ be a collection of trees such that $T_k$ has $k$ vertices. Can we always write $K_n$ as the edge disjoint union of the $T_k$?tree packing conjecture · graph theory · AI tried (unverified) · N/A#761The cochromatic number of $G$, denoted by $\zeta(G)$, is the minimum number of colours needed to colour the vertices of $G$ such that each colour class induces either a complete graph or empty graph. …graph theory · AI tried (unverified) · N/A#766Let $f(n;k,l)=\min \mathrm{ex}(n;G)$, where $G$ ranges over all graphs with $k$ vertices and $l$ edges.Give good estimates for $f(n;k,l)$ in the range $k<l\leq k^2/4$. For fixed $k$ and large $n$ …graph theory · AI tried (unverified) · possible#778Alice and Bob play a game on the edges of $K_n$, alternating colouring edges by red (Alice) and blue (Bob). Alice goes first, and wins if at the end the largest red clique is larger than any of the bl…graph theory · AI tried (unverified) · N/A#802Is it true that any $K_r$-free graph on $n$ vertices with average degree $t$ contains an independent set on\[\gg_r \frac{\log t}{t}n\]many vertices?graph theory · AI tried (unverified) · N/A#805For which functions $g(n)$ with $n>g(n)\geq (\log n)^2$ is there a graph on $n$ vertices in which every induced subgraph on $g(n)$ vertices contains a clique of size $\geq \log n$ and an independe…graph theory · AI tried (unverified) · possible#809Define the anti-Ramsey number $\chi_S(n,e,G)$ as the smallest $r$ such that there is a graph with $n$ vertices and $e$ edges with an $r$-colouring of its edges in which every copy of $G$ has entirely …graph theory · AI tried (unverified) · possible#810Does there exist some $\epsilon>0$ such that, for all sufficiently large $n$, there exists a graph $G$ on $n$ vertices with at least $\epsilon n^2$ many edges such that the edges can be coloured w…graph theory · AI tried (unverified) · possible#811Suppose $n\equiv 1\pmod{m}$. We say that an edge-colouring of $K_n$ using $m$ colours is balanced if every vertex sees exactly $\lfloor n/m\rfloor$ many edges of each colours. For which graphs $G$ is …graph theory · AI tried (unverified) · possible#813Let $h(n)$ be minimal such that every graph on $n$ vertices where every set of $7$ vertices contains a triangle (a copy of $K_3$) must contain a clique on at least $h(n)$ vertices. Estimate $h(n)$ - i…graph theory · AI tried (unverified) · possible#836Let $r\geq 2$ and $G$ be a $r$-uniform hypergraph with chromatic number $3$ (that is, there is a $3$-colouring of the vertices of $G$ such that no edge is monochromatic).Suppose any two edges of $G$ h…graph theory · AI tried (unverified) · N/A