Identifier
Mp00046:
Ordered trees
—to graph⟶
Graphs
Mp00324: Graphs —chromatic difference sequence⟶ Integer compositions
Mp00315: Integer compositions —inverse Foata bijection⟶ Integer compositions
Mp00324: Graphs —chromatic difference sequence⟶ Integer compositions
Mp00315: Integer compositions —inverse Foata bijection⟶ Integer compositions
Images
[] => ([],1) => [1] => [1]
[[]] => ([(0,1)],2) => [1,1] => [1,1]
[[],[]] => ([(0,2),(1,2)],3) => [2,1] => [2,1]
[[[]]] => ([(0,2),(1,2)],3) => [2,1] => [2,1]
[[],[],[]] => ([(0,3),(1,3),(2,3)],4) => [3,1] => [3,1]
[[],[[]]] => ([(0,3),(1,2),(2,3)],4) => [2,2] => [2,2]
[[[]],[]] => ([(0,3),(1,2),(2,3)],4) => [2,2] => [2,2]
[[[],[]]] => ([(0,3),(1,3),(2,3)],4) => [3,1] => [3,1]
[[[[]]]] => ([(0,3),(1,2),(2,3)],4) => [2,2] => [2,2]
[[],[],[],[]] => ([(0,4),(1,4),(2,4),(3,4)],5) => [4,1] => [4,1]
[[],[],[[]]] => ([(0,4),(1,4),(2,3),(3,4)],5) => [3,2] => [3,2]
[[],[[]],[]] => ([(0,4),(1,4),(2,3),(3,4)],5) => [3,2] => [3,2]
[[],[[],[]]] => ([(0,4),(1,4),(2,3),(3,4)],5) => [3,2] => [3,2]
[[],[[[]]]] => ([(0,4),(1,3),(2,3),(2,4)],5) => [3,2] => [3,2]
[[[]],[],[]] => ([(0,4),(1,4),(2,3),(3,4)],5) => [3,2] => [3,2]
[[[]],[[]]] => ([(0,4),(1,3),(2,3),(2,4)],5) => [3,2] => [3,2]
[[[],[]],[]] => ([(0,4),(1,4),(2,3),(3,4)],5) => [3,2] => [3,2]
[[[[]]],[]] => ([(0,4),(1,3),(2,3),(2,4)],5) => [3,2] => [3,2]
[[[],[],[]]] => ([(0,4),(1,4),(2,4),(3,4)],5) => [4,1] => [4,1]
[[[],[[]]]] => ([(0,4),(1,4),(2,3),(3,4)],5) => [3,2] => [3,2]
[[[[]],[]]] => ([(0,4),(1,4),(2,3),(3,4)],5) => [3,2] => [3,2]
[[[[],[]]]] => ([(0,4),(1,4),(2,3),(3,4)],5) => [3,2] => [3,2]
[[[[[]]]]] => ([(0,4),(1,3),(2,3),(2,4)],5) => [3,2] => [3,2]
[[],[],[],[],[]] => ([(0,5),(1,5),(2,5),(3,5),(4,5)],6) => [5,1] => [5,1]
[[],[],[],[[]]] => ([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => [4,2] => [4,2]
[[],[],[[]],[]] => ([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => [4,2] => [4,2]
[[],[],[[],[]]] => ([(0,5),(1,5),(2,4),(3,4),(4,5)],6) => [4,2] => [4,2]
[[],[],[[[]]]] => ([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => [4,2] => [4,2]
[[],[[]],[],[]] => ([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => [4,2] => [4,2]
[[],[[]],[[]]] => ([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => [3,3] => [3,3]
[[],[[],[]],[]] => ([(0,5),(1,5),(2,4),(3,4),(4,5)],6) => [4,2] => [4,2]
[[],[[[]]],[]] => ([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => [4,2] => [4,2]
[[],[[],[],[]]] => ([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => [4,2] => [4,2]
[[],[[],[[]]]] => ([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => [3,3] => [3,3]
[[],[[[]],[]]] => ([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => [3,3] => [3,3]
[[],[[[],[]]]] => ([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => [4,2] => [4,2]
[[],[[[[]]]]] => ([(0,5),(1,4),(2,3),(2,4),(3,5)],6) => [3,3] => [3,3]
[[[]],[],[],[]] => ([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => [4,2] => [4,2]
[[[]],[],[[]]] => ([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => [3,3] => [3,3]
[[[]],[[]],[]] => ([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => [3,3] => [3,3]
[[[]],[[],[]]] => ([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => [4,2] => [4,2]
[[[]],[[[]]]] => ([(0,5),(1,4),(2,3),(2,4),(3,5)],6) => [3,3] => [3,3]
[[[],[]],[],[]] => ([(0,5),(1,5),(2,4),(3,4),(4,5)],6) => [4,2] => [4,2]
[[[[]]],[],[]] => ([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => [4,2] => [4,2]
[[[],[]],[[]]] => ([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => [4,2] => [4,2]
[[[[]]],[[]]] => ([(0,5),(1,4),(2,3),(2,4),(3,5)],6) => [3,3] => [3,3]
[[[],[],[]],[]] => ([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => [4,2] => [4,2]
[[[],[[]]],[]] => ([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => [3,3] => [3,3]
[[[[]],[]],[]] => ([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => [3,3] => [3,3]
[[[[],[]]],[]] => ([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => [4,2] => [4,2]
[[[[[]]]],[]] => ([(0,5),(1,4),(2,3),(2,4),(3,5)],6) => [3,3] => [3,3]
[[[],[],[],[]]] => ([(0,5),(1,5),(2,5),(3,5),(4,5)],6) => [5,1] => [5,1]
[[[],[],[[]]]] => ([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => [4,2] => [4,2]
[[[],[[]],[]]] => ([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => [4,2] => [4,2]
[[[],[[],[]]]] => ([(0,5),(1,5),(2,4),(3,4),(4,5)],6) => [4,2] => [4,2]
[[[],[[[]]]]] => ([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => [4,2] => [4,2]
[[[[]],[],[]]] => ([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => [4,2] => [4,2]
[[[[]],[[]]]] => ([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => [3,3] => [3,3]
[[[[],[]],[]]] => ([(0,5),(1,5),(2,4),(3,4),(4,5)],6) => [4,2] => [4,2]
[[[[[]]],[]]] => ([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => [4,2] => [4,2]
[[[[],[],[]]]] => ([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => [4,2] => [4,2]
[[[[],[[]]]]] => ([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => [3,3] => [3,3]
[[[[[]],[]]]] => ([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => [3,3] => [3,3]
[[[[[],[]]]]] => ([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => [4,2] => [4,2]
[[[[[[]]]]]] => ([(0,5),(1,4),(2,3),(2,4),(3,5)],6) => [3,3] => [3,3]
[[],[],[],[],[],[]] => ([(0,6),(1,6),(2,6),(3,6),(4,6),(5,6)],7) => [6,1] => [6,1]
[[],[],[],[],[[]]] => ([(0,6),(1,6),(2,6),(3,6),(4,5),(5,6)],7) => [5,2] => [5,2]
[[],[],[],[[]],[]] => ([(0,6),(1,6),(2,6),(3,6),(4,5),(5,6)],7) => [5,2] => [5,2]
[[],[],[],[[],[]]] => ([(0,6),(1,6),(2,6),(3,5),(4,5),(5,6)],7) => [5,2] => [5,2]
[[],[],[],[[[]]]] => ([(0,6),(1,6),(2,6),(3,4),(4,5),(5,6)],7) => [5,2] => [5,2]
[[],[],[[]],[],[]] => ([(0,6),(1,6),(2,6),(3,6),(4,5),(5,6)],7) => [5,2] => [5,2]
[[],[],[[]],[[]]] => ([(0,6),(1,6),(2,5),(3,4),(4,6),(5,6)],7) => [4,3] => [4,3]
[[],[],[[],[]],[]] => ([(0,6),(1,6),(2,6),(3,5),(4,5),(5,6)],7) => [5,2] => [5,2]
[[],[],[[[]]],[]] => ([(0,6),(1,6),(2,6),(3,4),(4,5),(5,6)],7) => [5,2] => [5,2]
[[],[],[[],[],[]]] => ([(0,6),(1,6),(2,6),(3,5),(4,5),(5,6)],7) => [5,2] => [5,2]
[[],[],[[],[[]]]] => ([(0,6),(1,5),(2,5),(3,4),(4,6),(5,6)],7) => [4,3] => [4,3]
[[],[],[[[]],[]]] => ([(0,6),(1,5),(2,5),(3,4),(4,6),(5,6)],7) => [4,3] => [4,3]
[[],[],[[[],[]]]] => ([(0,6),(1,6),(2,5),(3,5),(4,5),(4,6)],7) => [5,2] => [5,2]
[[],[],[[[[]]]]] => ([(0,6),(1,6),(2,3),(3,5),(4,5),(4,6)],7) => [4,3] => [4,3]
[[],[[]],[],[],[]] => ([(0,6),(1,6),(2,6),(3,6),(4,5),(5,6)],7) => [5,2] => [5,2]
[[],[[]],[],[[]]] => ([(0,6),(1,6),(2,5),(3,4),(4,6),(5,6)],7) => [4,3] => [4,3]
[[],[[]],[[]],[]] => ([(0,6),(1,6),(2,5),(3,4),(4,6),(5,6)],7) => [4,3] => [4,3]
[[],[[]],[[],[]]] => ([(0,6),(1,5),(2,5),(3,4),(4,6),(5,6)],7) => [4,3] => [4,3]
[[],[[]],[[[]]]] => ([(0,6),(1,4),(2,3),(3,6),(4,5),(5,6)],7) => [4,3] => [4,3]
[[],[[],[]],[],[]] => ([(0,6),(1,6),(2,6),(3,5),(4,5),(5,6)],7) => [5,2] => [5,2]
[[],[[[]]],[],[]] => ([(0,6),(1,6),(2,6),(3,4),(4,5),(5,6)],7) => [5,2] => [5,2]
[[],[[],[]],[[]]] => ([(0,6),(1,5),(2,5),(3,4),(4,6),(5,6)],7) => [4,3] => [4,3]
[[],[[[]]],[[]]] => ([(0,6),(1,4),(2,3),(3,6),(4,5),(5,6)],7) => [4,3] => [4,3]
[[],[[],[],[]],[]] => ([(0,6),(1,6),(2,6),(3,5),(4,5),(5,6)],7) => [5,2] => [5,2]
[[],[[],[[]]],[]] => ([(0,6),(1,5),(2,5),(3,4),(4,6),(5,6)],7) => [4,3] => [4,3]
[[],[[[]],[]],[]] => ([(0,6),(1,5),(2,5),(3,4),(4,6),(5,6)],7) => [4,3] => [4,3]
[[],[[[],[]]],[]] => ([(0,6),(1,6),(2,5),(3,5),(4,5),(4,6)],7) => [5,2] => [5,2]
[[],[[[[]]]],[]] => ([(0,6),(1,6),(2,3),(3,5),(4,5),(4,6)],7) => [4,3] => [4,3]
[[],[[],[],[],[]]] => ([(0,6),(1,6),(2,6),(3,6),(4,5),(5,6)],7) => [5,2] => [5,2]
[[],[[],[],[[]]]] => ([(0,6),(1,6),(2,5),(3,4),(4,6),(5,6)],7) => [4,3] => [4,3]
[[],[[],[[]],[]]] => ([(0,6),(1,6),(2,5),(3,4),(4,6),(5,6)],7) => [4,3] => [4,3]
[[],[[],[[],[]]]] => ([(0,6),(1,5),(2,5),(3,4),(4,6),(5,6)],7) => [4,3] => [4,3]
[[],[[],[[[]]]]] => ([(0,6),(1,4),(2,3),(3,6),(4,5),(5,6)],7) => [4,3] => [4,3]
[[],[[[]],[],[]]] => ([(0,6),(1,6),(2,5),(3,4),(4,6),(5,6)],7) => [4,3] => [4,3]
[[],[[[]],[[]]]] => ([(0,5),(1,4),(2,3),(3,6),(4,6),(5,6)],7) => [4,3] => [4,3]
[[],[[[],[]],[]]] => ([(0,6),(1,5),(2,5),(3,4),(4,6),(5,6)],7) => [4,3] => [4,3]
>>> Load all 197 entries. <<<Map
to graph
Description
Return the undirected graph obtained from the tree nodes and edges.
Map
chromatic difference sequence
Description
The chromatic difference sequence of a graph.
Let $G$ be a simple graph with chromatic number $\kappa$. Let $\alpha_m$ be the maximum number of vertices in a $m$-colorable subgraph of $G$. Set $\delta_m=\alpha_m-\alpha_{m-1}$. The sequence $\delta_1,\delta_2,\dots\delta_\kappa$ is the chromatic difference sequence of $G$.
All entries of the chromatic difference sequence are positive: $\alpha_m > \alpha_{m-1}$ for $m < \kappa$, because we can assign any uncolored vertex of a partial coloring with $m-1$ colors the color $m$. Therefore, the chromatic difference sequence is a composition of the number of vertices of $G$ into $\kappa$ parts.
Let $G$ be a simple graph with chromatic number $\kappa$. Let $\alpha_m$ be the maximum number of vertices in a $m$-colorable subgraph of $G$. Set $\delta_m=\alpha_m-\alpha_{m-1}$. The sequence $\delta_1,\delta_2,\dots\delta_\kappa$ is the chromatic difference sequence of $G$.
All entries of the chromatic difference sequence are positive: $\alpha_m > \alpha_{m-1}$ for $m < \kappa$, because we can assign any uncolored vertex of a partial coloring with $m-1$ colors the color $m$. Therefore, the chromatic difference sequence is a composition of the number of vertices of $G$ into $\kappa$ parts.
Map
inverse Foata bijection
Description
The inverse of Foata's bijection.
See Mp00314Foata bijection.
See Mp00314Foata bijection.
searching the database
Sorry, this map was not found in the database.