![](/files/happy5.png)
tree
A gold-grabbing game ★★
Author(s): Rosenfeld
Setup Fix a tree and for every vertex
a non-negative integer
which we think of as the amount of gold at
.
2-Player game Players alternate turns. On each turn, a player chooses a leaf vertex of the tree, takes the gold at this vertex, and then deletes
. The game ends when the tree is empty, and the winner is the player who has accumulated the most gold.
Problem Find optimal strategies for the players.
Graphs with a forbidden induced tree are chi-bounded ★★★
Author(s): Gyarfas
Say that a family of graphs is
-bounded if there exists a function
so that every
satisfies
.
Conjecture For every fixed tree
, the family of graphs with no induced subgraph isomorphic to
is
-bounded.
![$ T $](/files/tex/79f55d2e1d83a7726c807a70cbe756713b0437b6.png)
![$ T $](/files/tex/79f55d2e1d83a7726c807a70cbe756713b0437b6.png)
![$ \chi $](/files/tex/0308ad82f7a52e8b5406c475bffba60ea6867b7a.png)
Keywords: chi-bounded; coloring; excluded subgraph; tree
Does the chromatic symmetric function distinguish between trees? ★★
Author(s): Stanley
Problem Do there exist non-isomorphic trees which have the same chromatic symmetric function?
Keywords: chromatic polynomial; symmetric function; tree
Graham's conjecture on tree reconstruction ★★
Author(s): Graham
Problem for every graph
, we let
denote the line graph of
. Given that
is a tree, can we determine it from the integer sequence
?
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ L(G) $](/files/tex/76f6ee75811ed6d89f7e99f8aa7a505f462c30b2.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ |V(G)|, |V(L(G))|, |V(L(L(G)))|, \ldots $](/files/tex/b93a7a2773f22770891c213297401ce7189f4fa2.png)
Keywords: reconstruction; tree
![Syndicate content Syndicate content](/misc/feed.png)