tree


A gold-grabbing game ★★

Author(s): Rosenfeld

\textbf{ Setup} Fix a tree $T$ and for every vertex $v \in V(T)$ a non-negative integer $g(v)$ which we think of as the amount of \emph{gold} at $v$.

\textbf{2-Player game} Players alternate turns. On each turn, a player chooses a leaf vertex $v$ of the tree, takes the gold at this vertex, and then deletes $v$. The game ends when the tree is empty, and the winner is the player who has accumulated the most gold.

\begin{problem} Find optimal strategies for the players. \end{problem}

Keywords: game; tree

Graphs with a forbidden induced tree are chi-bounded ★★★

Author(s): Gyarfas

Say that a family ${\mathcal F}$ of graphs is $\chi$-\emph{bounded} if there exists a function $f: {\mathbb N} \rightarrow {\mathbb N}$ so that every $G \in {\mathcal F}$ satisfies $\chi(G) \le f (\omega(G))$.

\begin{conjecture} For every fixed tree $T$, the family of graphs with no induced subgraph isomorphic to $T$ is $\chi$-bounded. \end{conjecture}

Keywords: chi-bounded; coloring; excluded subgraph; tree

Does the chromatic symmetric function distinguish between trees? ★★

Author(s): Stanley

\begin{problem} Do there exist non-isomorphic trees which have the same chromatic symmetric function? \end{problem}

Keywords: chromatic polynomial; symmetric function; tree

Graham's conjecture on tree reconstruction ★★

Author(s): Graham

\begin{problem} for every graph $G$, we let $L(G)$ denote the \Def{line graph} of $G$. Given that $G$ is a tree, can we determine it from the integer sequence $|V(G)|, |V(L(G))|, |V(L(L(G)))|, \ldots$? \end{problem}

Keywords: reconstruction; tree

Syndicate content