Open Problem Garden

Coloring random subgraphs ★★

Author(s): Bukh

If $G$ is a graph and $p \in [0,1]$ , we let $G_p$ denote a subgraph of $G$ where each edge of $G$ appears in $G_p$ with independently with probability $p$ .

Problem Does there exist a constant $c$ so that ${\mathbb E}(\chi(G_{1/2})) > c \frac{\chi(G)}{\log \chi(G)}$ ?

Keywords: coloring; random graph

Posted by mdevos
updated June 4th, 2009

1 comment

Bukh, Boris

random graph

Graph Theory » Basic G.T.

Complete bipartite subgraphs of perfect graphs ★★

Author(s): Fox

Problem Let $G$ be a perfect graph on $n$ vertices. Is it true that either $G$ or $\bar{G}$ contains a complete bipartite subgraph with bipartition $(A,B)$ so that $|A|, |B| \ge n^{1 - o(1)}$ ?

Keywords: perfect graph

Posted by mdevos
updated January 19th, 2021

1 comment

Graph Theory » Algebraic G.T.

Cores of strongly regular graphs ★★★

Author(s): Cameron; Kazanidis

Question Does every strongly regular graph have either itself or a complete graph as a core?

Keywords: core; strongly regular

Posted by mdevos
updated October 18th, 2011

1 comment

Kazanidis, Priscila A.

Number Theory » Computational N.T.

Wall-Sun-Sun primes and Fibonacci divisibility ★★

Author(s):

Conjecture For any prime $p$ , there exists a Fibonacci number divisible by $p$ exactly once.

Equivalently:

Conjecture For any prime $p>5$ , $p^2$ does not divide $F_{p-\left(\frac p5\right)}$ where $\left(\frac mn\right)$ is the Legendre symbol.

Keywords: Fibonacci; prime

Posted by adudzik
updated June 14th, 2008

add new comment

Fibonacci

Number Theory

A discrete iteration related to Pierce expansions ★★

Author(s): Shallit

Conjecture Let $a > b > 0$ be integers. Set $b_1 = b$ and $b_{i+1} = {a \bmod {b_i}}$ for $i \geq 0$ . Eventually we have $b_{n+1} = 0$ ; put $P(a,b) = n$ .

Example: $P(35, 22) = 7$ , since $b_1 = 22$ , $b_2 = 13$ , $b_3 = 9$ , $b_4 = 8$ , $b_5 = 3$ , $b_6 = 2$ , $b_7 = 1$ , $b_8 = 0$ .