I looked into this issue, and also discussed with mfo.

The sos code that fails compilation due to the python 3.6 package not yet being installed is,

    @staticmethod
    def _query_address(url: str) -> HTTPResponse:
        """
        Query the given url address with headers required by Google Metadata
        Server.
        """
        try:
            req = request.Request(url, headers={'Metadata-Flavor': 'Google'})
            response = request.urlopen(req)
        except URLError as err:
            raise RuntimeError(
                "Failed to communicate with Metadata Server: " + str(err))
        if response.code != 200:
            raise RuntimeError(
                f"Failed to communicate with Metadata Server " <---
                f"(code: {response.code}): " + response.read().decode()) <----
        return response

We have decided to hold off the 4.5.6 release on bionic since 4.5.6 has many more plugins using f strings.

For this version, it's just the gcp plugin that has f strings in the bionic sos. But 4.5.6 source has more than hundred instances (https://pastebin.canonical.com/p/8DpdjwWKM4/)

Looking further,

The generated postinst tries to build py3compile sosreport, (Thanks mfo for this info!)

$ pull-lp-debs sosreport bionic 4.4-1ubuntu0.18.04.1
Found sosreport 4.4-1ubuntu0.18.04.1 in bionic
Downloading sosreport_4.4-1ubuntu0.18.04.1_amd64.deb from archive.ubuntu.com (0.291 MiB)
[=====================================================>]100%
:~/Downloads/dpkgtest$ mkdir ext
:~/Downloads/dpkgtest$ dpkg-deb -e  
ext/                                      sosreport_4.4-1ubuntu0.18.04.1_amd64.deb  
:~/Downloads/dpkgtest$ dpkg-deb -e  sosreport_4.4-1ubuntu0.18.04.1_amd64.deb ext/
:~/Downloads/dpkgtest$ cd ext/
:~/Downloads/dpkgtest/ext$ ls
conffiles  control  md5sums  postinst  prerm
:~/Downloads/dpkgtest/ext$ cat postinst 
#!/bin/sh
set -e

# Automatically added by dh_python3:
if which py3compile >/dev/null 2>&1; then
	py3compile -p sosreport  <----
fi

# End automatically added section

There's a couple of things we can do for a fix. 

Either have the depends in the control file using something like python3 (>= 3.6.5-3) which might be an easier fix, or try to generate a check additionally in the postinst that dh_python generates, that does not compile sos if the version is bionic and python 3.6 isn't available.

The series after bionic seem fine, 

# rmadison python3
 python3 | 3.4.0-0ubuntu2  | trusty         | amd64, arm64, armhf, i386, powerpc, ppc64el
 python3 | 3.5.1-3         | xenial         | amd64, arm64, armhf, i386, powerpc, ppc64el, s390x
 python3 | 3.6.5-3         | bionic         | amd64, arm64, armhf, i386, ppc64el, s390x
 python3 | 3.6.7-1~18.04   | bionic-updates | amd64, arm64, armhf, i386, ppc64el, s390x
 python3 | 3.8.2-0ubuntu2  | focal          | amd64, arm64, armhf, i386, ppc64el, riscv64, s390x
 python3 | 3.10.4-0ubuntu2 | jammy          | amd64, arm64, armhf, i386, ppc64el, riscv64, s390x
 python3 | 3.10.6-1~22.04  | jammy-security | amd64, arm64, armhf, i386, ppc64el, riscv64, s390x
 python3 | 3.10.6-1~22.04  | jammy-updates  | amd64, arm64, armhf, i386, ppc64el, riscv64, s390x
 python3 | 3.11.2-1        | lunar          | amd64, arm64, armhf, i386, ppc64el, riscv64, s390x
 python3 | 3.11.4-5        | mantic         | amd64, arm64, armhf, i386, ppc64el, riscv64, s390x
 python3 | 3.11.4-5        | noble          | amd64, arm64, armhf, i386, ppc64el, riscv64, s390x