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 $.

Prove or disprove: $ P(a,b) = O((\log a)^2) $.

Keywords: Pierce expansions

Posted by shallit
updated May 30th, 2020
2 comments
Graph Theory » Coloring

Total Colouring Conjecture ★★★

Author(s): Behzad

Conjecture   A total coloring of a graph $ G = (V,E) $ is an assignment of colors to the vertices and the edges of $ G $ such that every pair of adjacent vertices, every pair of adjacent edges and every vertex and incident edge pair, receive different colors. The total chromatic number of a graph $ G $, $ \chi''(G) $, equals the minimum number of colors needed in a total coloring of $ G $. It is an old conjecture of Behzad that for every graph $ G $, the total chromatic number equals the maximum degree of a vertex in $ G $, $ \Delta(G) $ plus one or two. In other words, \[\chi''(G)=\Delta(G)+1\ \ or \ \ \Delta(G)+2.\]

Keywords: Total coloring

Posted by Iradmusa
updated June 4th, 2008
add new comment