AI MENUMBANGKAN KONJEKTUR PEWARNAAN DARI TAHUN 1990-AN

Ambillah sebuah jaringan titik-titik yang dihubungkan garis — sebuah graf. Pewarnaan total memberi warna pada setiap titik dan setiap garis, mengikuti tiga aturan: dua titik bertetangga harus berbeda, dua garis yang bertemu di satu titik harus berbeda, dan sebuah garis harus berbeda dari kedua titik ujungnya. Jumlah warna terkecil yang memenuhi disebut bilangan kromatik total, ditulis χ″(G).

Sekarang buat lebih sulit. Berikan setiap titik dan setiap garis daftarnya sendiri berisi warna yang diizinkan, semua daftar berukuran sama k, lalu tuntut pewarnaan yang sah yang dipilih dari daftar-daftar itu. k terkecil yang berhasil apa pun daftarnya adalah bilangan kromatik total daftar, χ″ℓ(G). Bilangan ini tidak pernah bisa lebih kecil daripada χ″(G): jika semua daftar identik, kita kembali ke masalah biasa.

Konjektur dari akhir 1990-an

Tiga kelompok — Borodin, Kostochka, dan Woodall; Juvan, Mohar, dan Škrekovski; Hilton dan Johnson — secara terpisah mengusulkan, pada akhir 1990-an, bahwa daftar pribadi tidak pernah menuntut apa pun:

χ″ℓ(G) = χ″(G) untuk setiap graf (bahkan dengan beberapa garis di antara dua titik).

Inilah Konjektur Pewarnaan Total Daftar (List Total Colouring Conjecture). Bukti-bukti mendukungnya: konjektur ini berlaku untuk graf yang tidak satu pun titiknya memiliki lebih dari dua garis, dan setiap graf dengan tepat tiga garis per titik (graf kubik) diketahui memerlukan paling banyak 5 warna dari daftar.

Contoh penyangkal

Jonathan Noel dari Universitas Victoria di Kanada kini menunjukkan sebuah graf kubik dengan 20 titik yang memiliki χ″ = 4 tetapi χ″ℓ = 5. Konjektur itu salah.

Konstruksinya ringkas. Ambil empat salinan graf kecil bernama K₂,₃: dua titik “pribadi”, masing-masing terhubung ke tiga titik “terminal” yang sama. Lalu hubungkan setiap pasangan salinan dengan tepat satu garis “silang” di antara terminal. Setiap titik akhirnya memiliki tiga garis.

Graf 20 titik yang digambar sebagai empat blok yang dihubungkan garis silang, diwarnai dengan empat warna.

Graf G dengan pewarnaan total hanya dalam empat warna, ditunjukkan dengan bentuk dan gaya garis. — Gambar 1, Noel (2026), arXiv:2609.38417.

Empat warna cukup dalam permainan biasa: warna 4 diberikan kepada semua titik pribadi dan semua garis silang, yang tidak pernah bersentuhan satu sama lain, sementara sebuah tabel kecil dan aturan siklik menangani sisanya.

Daftar yang tidak mungkin dipenuhi

Jebakannya memakai warna 1 hingga 5. Setiap titik dan garis di blok i mendapat daftar “semua warna kecuali i”; garis-garis silang mendapat daftar yang dipilih dengan cermat, yang tidak memuat 5 atau i + 2. Buktinya lalu berjalan seperti cerita detektif pendek:

Lema: dalam pewarnaan-4 apa pun pada K₂,₃, kedua titik pribadi harus berwarna sama.
Jadi setiap blok i memiliki sepasang warna {i, sᵢ}, dan setiap garis silang di antara dua blok harus memakai warna yang dimiliki kedua pasangan itu.
Sedikit perhitungan menunjukkan bahwa satu warna t harus termasuk dalam keempat pasangan.
Untuk setiap kemungkinan t, satu garis silang tertentu mendapati warna itu tidak ada dalam daftarnya. Kontradiksi.

Graf yang sama dengan setiap titik dan garis ditandai oleh warna yang tidak ada dalam daftarnya.

Penetapan daftar: setiap titik dan garis boleh memakai semua warna dari 1 hingga 5 kecuali yang ditunjukkan. Tidak ada pewarnaan total yang dapat mematuhi daftar-daftar ini. — Gambar 2, Noel (2026), arXiv:2609.38417.

Ditemukan mesin, diperiksa matematikawan

Makalah ini luar biasa terbuka tentang asal-usulnya. Pada 24 September 2026, Noel meminta ChatGPT 6 Astra Ultra untuk membantah konjektur itu, dan model itu menghasilkan contoh penyangkalnya, “dengan sedikit masukan dari penulis”. Noel memeriksa argumen-argumennya dan menulis ulang teksnya dari draf yang dihasilkan model; model itu juga membantu mengoreksi, menyarankan referensi, dan menggambar ilustrasinya. “Penulis memikul tanggung jawab penuh atas kebenarannya,” demikian pernyataan itu diakhiri. Makalah ini masih berupa pracetak, tetapi buktinya cukup pendek untuk diperiksa oleh pembaca mana pun yang sabar.

Selisih satu, atau lebih?

Daftar pribadi bisa menuntut satu warna tambahan. Bisakah menuntut lebih? Selisih tiga juga akan menumbangkan kerabatnya yang banyak dipelajari, Konjektur Pewarnaan Sisi Daftar (List Edge Colouring Conjecture), karena χ″ℓ ≤ χ′ℓ + 2 dan χ″ ≥ χ′. Noel menutup dengan pertanyaan terbuka yang tetap berdiri setelah contoh penyangkal dari AI itu: apakah χ″ℓ(G) ≤ χ″(G) + 1 untuk setiap graf?