When you encountered the error message:
mysql-server-5.6 : Depends: mysql-client-5.6 (>= 5.6.19-1~dotdeb.1) but it is not going to be installed
during MySql update from 5.5 to 5.6 version, you should do:
sudo apt-get install mysql-common=5.6.19-1~dotdeb.1
You can also check all available version with:
sudo apt-cache showpkg mysql-common