Identifier
Mp00184: Integer compositions —to threshold graph⟶ Graphs
Mp00324: Graphs —chromatic difference sequence⟶ Integer compositions
Mp00173: Integer compositions —rotate front to back⟶ Integer compositions
Images
=>
Cc0020;cc-rep-1
[1]=>([],1)=>[1]=>[1] [1,1]=>([(0,1)],2)=>[1,1]=>[1,1] [2]=>([],2)=>[2]=>[2] [1,1,1]=>([(0,1),(0,2),(1,2)],3)=>[1,1,1]=>[1,1,1] [1,2]=>([(1,2)],3)=>[2,1]=>[1,2] [2,1]=>([(0,2),(1,2)],3)=>[2,1]=>[1,2] [3]=>([],3)=>[3]=>[3] [1,1,1,1]=>([(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)],4)=>[1,1,1,1]=>[1,1,1,1] [1,1,2]=>([(1,2),(1,3),(2,3)],4)=>[2,1,1]=>[1,1,2] [1,2,1]=>([(0,3),(1,2),(1,3),(2,3)],4)=>[2,1,1]=>[1,1,2] [1,3]=>([(2,3)],4)=>[3,1]=>[1,3] [2,1,1]=>([(0,2),(0,3),(1,2),(1,3),(2,3)],4)=>[2,1,1]=>[1,1,2] [2,2]=>([(1,3),(2,3)],4)=>[3,1]=>[1,3] [3,1]=>([(0,3),(1,3),(2,3)],4)=>[3,1]=>[1,3] [4]=>([],4)=>[4]=>[4] [1,1,1,1,1]=>([(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>[1,1,1,1,1]=>[1,1,1,1,1] [1,1,1,2]=>([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>[2,1,1,1]=>[1,1,1,2] [1,1,2,1]=>([(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>[2,1,1,1]=>[1,1,1,2] [1,1,3]=>([(2,3),(2,4),(3,4)],5)=>[3,1,1]=>[1,1,3] [1,2,1,1]=>([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>[2,1,1,1]=>[1,1,1,2] [1,2,2]=>([(1,4),(2,3),(2,4),(3,4)],5)=>[3,1,1]=>[1,1,3] [1,3,1]=>([(0,4),(1,4),(2,3),(2,4),(3,4)],5)=>[3,1,1]=>[1,1,3] [1,4]=>([(3,4)],5)=>[4,1]=>[1,4] [2,1,1,1]=>([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>[2,1,1,1]=>[1,1,1,2] [2,1,2]=>([(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>[3,1,1]=>[1,1,3] [2,2,1]=>([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>[3,1,1]=>[1,1,3] [2,3]=>([(2,4),(3,4)],5)=>[4,1]=>[1,4] [3,1,1]=>([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>[3,1,1]=>[1,1,3] [3,2]=>([(1,4),(2,4),(3,4)],5)=>[4,1]=>[1,4] [4,1]=>([(0,4),(1,4),(2,4),(3,4)],5)=>[4,1]=>[1,4] [5]=>([],5)=>[5]=>[5] [1,1,1,1,1,1]=>([(0,1),(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>[1,1,1,1,1,1]=>[1,1,1,1,1,1] [1,1,1,1,2]=>([(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>[2,1,1,1,1]=>[1,1,1,1,2] [1,1,1,2,1]=>([(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>[2,1,1,1,1]=>[1,1,1,1,2] [1,1,1,3]=>([(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>[3,1,1,1]=>[1,1,1,3] [1,1,2,1,1]=>([(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>[2,1,1,1,1]=>[1,1,1,1,2] [1,1,2,2]=>([(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>[3,1,1,1]=>[1,1,1,3] [1,1,3,1]=>([(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>[3,1,1,1]=>[1,1,1,3] [1,1,4]=>([(3,4),(3,5),(4,5)],6)=>[4,1,1]=>[1,1,4] [1,2,1,1,1]=>([(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>[2,1,1,1,1]=>[1,1,1,1,2] [1,2,1,2]=>([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>[3,1,1,1]=>[1,1,1,3] [1,2,2,1]=>([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>[3,1,1,1]=>[1,1,1,3] [1,2,3]=>([(2,5),(3,4),(3,5),(4,5)],6)=>[4,1,1]=>[1,1,4] [1,3,1,1]=>([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>[3,1,1,1]=>[1,1,1,3] [1,3,2]=>([(1,5),(2,5),(3,4),(3,5),(4,5)],6)=>[4,1,1]=>[1,1,4] [1,4,1]=>([(0,5),(1,5),(2,5),(3,4),(3,5),(4,5)],6)=>[4,1,1]=>[1,1,4] [1,5]=>([(4,5)],6)=>[5,1]=>[1,5] [2,1,1,1,1]=>([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>[2,1,1,1,1]=>[1,1,1,1,2] [2,1,1,2]=>([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>[3,1,1,1]=>[1,1,1,3] [2,1,2,1]=>([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>[3,1,1,1]=>[1,1,1,3] [2,1,3]=>([(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>[4,1,1]=>[1,1,4] [2,2,1,1]=>([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>[3,1,1,1]=>[1,1,1,3] [2,2,2]=>([(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>[4,1,1]=>[1,1,4] [2,3,1]=>([(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>[4,1,1]=>[1,1,4] [2,4]=>([(3,5),(4,5)],6)=>[5,1]=>[1,5] [3,1,1,1]=>([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>[3,1,1,1]=>[1,1,1,3] [3,1,2]=>([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>[4,1,1]=>[1,1,4] [3,2,1]=>([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>[4,1,1]=>[1,1,4] [3,3]=>([(2,5),(3,5),(4,5)],6)=>[5,1]=>[1,5] [4,1,1]=>([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>[4,1,1]=>[1,1,4] [4,2]=>([(1,5),(2,5),(3,5),(4,5)],6)=>[5,1]=>[1,5] [5,1]=>([(0,5),(1,5),(2,5),(3,5),(4,5)],6)=>[5,1]=>[1,5] [6]=>([],6)=>[6]=>[6] [1,1,1,1,1,1,1]=>([(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(1,2),(1,3),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[1,1,1,1,1,1,1]=>[1,1,1,1,1,1,1] [1,1,1,1,1,2]=>([(1,2),(1,3),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[2,1,1,1,1,1]=>[1,1,1,1,1,2] [1,1,1,1,2,1]=>([(0,6),(1,2),(1,3),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[2,1,1,1,1,1]=>[1,1,1,1,1,2] [1,1,1,1,3]=>([(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[3,1,1,1,1]=>[1,1,1,1,3] [1,1,1,2,1,1]=>([(0,5),(0,6),(1,2),(1,3),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[2,1,1,1,1,1]=>[1,1,1,1,1,2] [1,1,1,2,2]=>([(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[3,1,1,1,1]=>[1,1,1,1,3] [1,1,1,3,1]=>([(0,6),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[3,1,1,1,1]=>[1,1,1,1,3] [1,1,1,4]=>([(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[4,1,1,1]=>[1,1,1,4] [1,1,2,1,1,1]=>([(0,4),(0,5),(0,6),(1,2),(1,3),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[2,1,1,1,1,1]=>[1,1,1,1,1,2] [1,1,2,1,2]=>([(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[3,1,1,1,1]=>[1,1,1,1,3] [1,1,2,2,1]=>([(0,6),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[3,1,1,1,1]=>[1,1,1,1,3] [1,1,2,3]=>([(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[4,1,1,1]=>[1,1,1,4] [1,1,3,1,1]=>([(0,5),(0,6),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[3,1,1,1,1]=>[1,1,1,1,3] [1,1,3,2]=>([(1,6),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[4,1,1,1]=>[1,1,1,4] [1,1,4,1]=>([(0,6),(1,6),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[4,1,1,1]=>[1,1,1,4] [1,1,5]=>([(4,5),(4,6),(5,6)],7)=>[5,1,1]=>[1,1,5] [1,2,1,1,1,1]=>([(0,3),(0,4),(0,5),(0,6),(1,2),(1,3),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[2,1,1,1,1,1]=>[1,1,1,1,1,2] [1,2,1,1,2]=>([(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[3,1,1,1,1]=>[1,1,1,1,3] [1,2,1,2,1]=>([(0,6),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[3,1,1,1,1]=>[1,1,1,1,3] [1,2,1,3]=>([(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[4,1,1,1]=>[1,1,1,4] [1,2,2,1,1]=>([(0,5),(0,6),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[3,1,1,1,1]=>[1,1,1,1,3] [1,2,2,2]=>([(1,6),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[4,1,1,1]=>[1,1,1,4] [1,2,3,1]=>([(0,6),(1,6),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[4,1,1,1]=>[1,1,1,4] [1,2,4]=>([(3,6),(4,5),(4,6),(5,6)],7)=>[5,1,1]=>[1,1,5] [1,3,1,1,1]=>([(0,4),(0,5),(0,6),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[3,1,1,1,1]=>[1,1,1,1,3] [1,3,1,2]=>([(1,5),(1,6),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[4,1,1,1]=>[1,1,1,4] [1,3,2,1]=>([(0,6),(1,5),(1,6),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[4,1,1,1]=>[1,1,1,4] [1,3,3]=>([(2,6),(3,6),(4,5),(4,6),(5,6)],7)=>[5,1,1]=>[1,1,5] [1,4,1,1]=>([(0,5),(0,6),(1,5),(1,6),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[4,1,1,1]=>[1,1,1,4] [1,4,2]=>([(1,6),(2,6),(3,6),(4,5),(4,6),(5,6)],7)=>[5,1,1]=>[1,1,5] [1,5,1]=>([(0,6),(1,6),(2,6),(3,6),(4,5),(4,6),(5,6)],7)=>[5,1,1]=>[1,1,5] [1,6]=>([(5,6)],7)=>[6,1]=>[1,6] [2,1,1,1,1,1]=>([(0,2),(0,3),(0,4),(0,5),(0,6),(1,2),(1,3),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[2,1,1,1,1,1]=>[1,1,1,1,1,2] [2,1,1,1,2]=>([(1,3),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[3,1,1,1,1]=>[1,1,1,1,3] [2,1,1,2,1]=>([(0,6),(1,3),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[3,1,1,1,1]=>[1,1,1,1,3] [2,1,1,3]=>([(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[4,1,1,1]=>[1,1,1,4] [2,1,2,1,1]=>([(0,5),(0,6),(1,3),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[3,1,1,1,1]=>[1,1,1,1,3] [2,1,2,2]=>([(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[4,1,1,1]=>[1,1,1,4] [2,1,3,1]=>([(0,6),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[4,1,1,1]=>[1,1,1,4] [2,1,4]=>([(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[5,1,1]=>[1,1,5] [2,2,1,1,1]=>([(0,4),(0,5),(0,6),(1,3),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[3,1,1,1,1]=>[1,1,1,1,3] [2,2,1,2]=>([(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[4,1,1,1]=>[1,1,1,4] [2,2,2,1]=>([(0,6),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[4,1,1,1]=>[1,1,1,4] [2,2,3]=>([(2,6),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[5,1,1]=>[1,1,5] [2,3,1,1]=>([(0,5),(0,6),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[4,1,1,1]=>[1,1,1,4] [2,3,2]=>([(1,6),(2,6),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[5,1,1]=>[1,1,5] [2,4,1]=>([(0,6),(1,6),(2,6),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[5,1,1]=>[1,1,5] [2,5]=>([(4,6),(5,6)],7)=>[6,1]=>[1,6] [3,1,1,1,1]=>([(0,3),(0,4),(0,5),(0,6),(1,3),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[3,1,1,1,1]=>[1,1,1,1,3] [3,1,1,2]=>([(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[4,1,1,1]=>[1,1,1,4] [3,1,2,1]=>([(0,6),(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[4,1,1,1]=>[1,1,1,4] [3,1,3]=>([(2,5),(2,6),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[5,1,1]=>[1,1,5] [3,2,1,1]=>([(0,5),(0,6),(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[4,1,1,1]=>[1,1,1,4] [3,2,2]=>([(1,6),(2,5),(2,6),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[5,1,1]=>[1,1,5] [3,3,1]=>([(0,6),(1,6),(2,5),(2,6),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[5,1,1]=>[1,1,5] [3,4]=>([(3,6),(4,6),(5,6)],7)=>[6,1]=>[1,6] [4,1,1,1]=>([(0,4),(0,5),(0,6),(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[4,1,1,1]=>[1,1,1,4] [4,1,2]=>([(1,5),(1,6),(2,5),(2,6),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[5,1,1]=>[1,1,5] [4,2,1]=>([(0,6),(1,5),(1,6),(2,5),(2,6),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[5,1,1]=>[1,1,5] [4,3]=>([(2,6),(3,6),(4,6),(5,6)],7)=>[6,1]=>[1,6] [5,1,1]=>([(0,5),(0,6),(1,5),(1,6),(2,5),(2,6),(3,5),(3,6),(4,5),(4,6),(5,6)],7)=>[5,1,1]=>[1,1,5] [5,2]=>([(1,6),(2,6),(3,6),(4,6),(5,6)],7)=>[6,1]=>[1,6] [6,1]=>([(0,6),(1,6),(2,6),(3,6),(4,6),(5,6)],7)=>[6,1]=>[1,6] [7]=>([],7)=>[7]=>[7]
Map
to threshold graph
Description
The threshold graph corresponding to the composition.
A threshold graph is a graph that can be obtained from the empty graph by adding successively isolated and dominating vertices.
A threshold graph is uniquely determined by its degree sequence.
The Laplacian spectrum of a threshold graph is integral. Interpreting it as an integer partition, it is the conjugate of the partition given by its degree sequence.
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.
Map
rotate front to back
Description
The front to back rotation of the entries of an integer composition.