b'\n_START_ARTICLE_\nVir\xc5\xa1\xc5\xabni\xc5\xb3 spalvinimas\n_START_PARAGRAPH_\nVir\xc5\xa1\xc5\xabni\xc5\xb3 spalvinimas - grafo spalvinimo variantas, kai grafo vir\xc5\xa1\xc5\xabn\xc4\x97ms priskiriamos spalvos taip, kad gretimos vir\xc5\xa1\xc5\xabn\xc4\x97s tur\xc4\x97t\xc5\xb3 skirtingas spalvas.\n_START_SECTION_\nChromatinis skai\xc4\x8dius\n_START_PARAGRAPH_\nMa\xc5\xbeiausias skai\xc4\x8dius spalv\xc5\xb3, kuriomis galima nuda\xc5\xbeyti grafo vir\xc5\xa1\xc5\xabnes, vadinamas grafo chromatiniu skai\xc4\x8diumi._NEWLINE_Esama \xc4\xafvairi\xc5\xb3 grafo chromatinio skai\xc4\x8diaus \xc4\xafver\xc4\x8di\xc5\xb3. Pavyzd\xc5\xbeiui, keturi\xc5\xb3 spalv\xc5\xb3 teorema teigia, kad plok\xc5\xa1\xc4\x8diojo grafo chromatinis skai\xc4\x8dius nevir\xc5\xa1ija keturi\xc5\xb3.\n_START_SECTION_\nAlgoritmai\n_START_PARAGRAPH_\nBendru atveju patikrinti, ar n vir\xc5\xa1\xc5\xabni\xc5\xb3 turintis grafas gali b\xc5\xabti nuda\xc5\xbeytas k spalv\xc5\xb3 galima per\xc5\xbei\xc5\xabrint visus derinius i\xc5\xa1 n element\xc5\xb3 po k (kiekvienai vir\xc5\xa1\xc5\xabnei priskiriama viena i\xc5\xa1 k spalv\xc5\xb3). Ie\xc5\xa1kant chromatinio skai\xc4\x8diaus tokius patikrinimus reikia atlikti k reik\xc5\xa1m\xc4\x97ms nuo 1 iki n, tad algoritmo laikinis sud\xc4\x97tingumas yra O((n+1)!)._NEWLINE_Kadangi tikslus algoritmas yra l\xc4\x97tas, paprastai naudojami euristiniai algoritmai.'