Ghet I used a google account to log into google maps. But now when I open the play store, it shows me as logged in there as well.
Shouldn't this be impossible?
No. It is a documented feature of Android: https://discuss.grapheneos.org/d/8553-auto-login-in-amazon-app-right-after-installation
Ghet I thought apps on graphene weren't supposed to communicate with each other.
No. Voluntary inter-app communication within a single profile is a normal feature of Android.
If you have specific information restriction requirements, it may be useful to read up on how the system works before using it a lot based on incorrect assumptions. Reading the material on the GrapheneOS web site might be useful.