Մասնակից:Հակոբջանյան Լիլիթ/Գրաֆների գունավորում

Գրաֆի գագաթների գունավորում գույների նվազագույն քանակով (երեք գույն)

Գրաֆների ներկում, գրաֆիկական-տեսական կառույց, գրաֆի գծանշման հատուկ դեպք: Ներկելիս գրաֆի տարրերին հատկացվում են որոշակի սահմանափակումներ և համապատասխան պիտակներ։ Այդ պիտակները ավանդաբար կոչվում են «գույներ»: Ամենապարզ դեպքում գրաֆիկի ուղղահայաց ներկման այս մեթոդը, որում տարբեր գույները համապատասխանում են ցանկացած երկու հարակից ուղղաձիգներին, կոչվում է կողային ներկում: Նմանապես, կողերի երանգավորումը յուրաքանչյուր կողին տալիս է գույն, որպեսզի հարակից ցանկացած կողերը ունենան տարբեր գույներ: Այլ կերպ ասած, ճիշտ գագաթային ներկումն այնպիսի ներկում է, որի դեպքում հարևան գագաթները ներկվում են տարբեր գույներով:

Ուղղահայաց ներկումը գրաֆիկի ներկման հիմնական խնդիրն է, այս ոլորտում մնացած բոլոր խնդիրները կարող են դրանով կրճատվել: Օրինակ, գրաֆիկի կողերի ներկումը նրա կողային գրաֆիկի ուղղահայաց ներկումն է, իսկ պլանային գրաֆով գագաթների գունավորումն իր երկակի գրաֆիկի ուղղահայաց երանգների ներկումն է: Այնուամենայնիվ, գրաֆիկի ներկման այլ խնդիրներ հաճախ առաջանում և լուծվում են բնօրինակ պարամետրում: Դրա պատճառը մասամբ այն է, որ այն ավելի լավ պատկերացում է տալիս կատարվածի մասին և ավելի բացահայտում է, իսկ մասամբ նաև այն պատճառով, որ որոշ առաջադրանքներ առավել հարմար են այս եղանակով լուծելու համար (օրինակ՝ կողերի գունազարդում):

Գունազարդման գրաֆիկները նույնպես օգտագործվում են շատ գործնական բնագավառներում և ոչ միայն տեսական խնդիրների մեջ: Խնդիրների դասական տեսակներից բացի, տարբեր սահմանափակումներ կարող են տեղադրվել նաև գրաֆում, գույների նշանակման ձևի կամ հենց գույների վրա: Այս մեթոդը, օրինակ, օգտագործվում է հանրաճանաչ սուդոկու հանելուկում: Այս ոլորտում դեռևս ակտիվ հետազոտություններ են ընթանում:

Պատմություն

Առաջին արդյունքները ստացվել են քարտեզների գունավորման խնդրի հարթ գրաֆիկների գունավորման համար: Փորձելով գունավորել Անգլիայի գավառների քարտեզը՝ Ֆրանցիսկ Գութին ձևակերպեց չորս գույնի ներկման խնդիրը՝ նշելով, որ չորս գույները բավարար են քարտեզը գունավորելու համար, որպեսզի հարակից ցանկացած երկու գագաթ ունենան տարբեր գույներ: Նրա եղբայրը հարցը ուղղեց իր մաթեմատիկայի ուսուցչին ՝ Օգոստուս Դե Մորգանին, ով դա նշեց 1852 թվականին Ուիլյամ Հեմիլթոնին ուղղված նամակում: Արթուր Քեյլին այս հարցը բարձրացրեց 1878 թվականին Լոնդոնի մաթեմատիկական ընկերության ժողովում: Նույն թվականին Թեյթը առաջարկել է այս խնդրի առաջին լուծումը: Նա նվազեցրեց բնօրինակ գրաֆիկի ուղղահայաց գունավորումը երկակի գրաֆիկի կողերի գունավորմանը և առաջարկեց, որ այս խնդիրը միշտ լուծում ունենա: 1880 թվականին Ալֆրեդ Քեմպեն հրապարակեց մի հոդված, որում ասվում է, որ նրան հաջողվել է և մի տասնամյակի ընթացքում չորս գույնի ներկման խնդիրը համարվել է լուծված: Այս նվաճման համար Քեմփեն ընտրվեց Լոնդոնի թագավորական հասարակության անդամ, իսկ ավելի ուշ՝ որպես Լոնդոնի մաթեմատիկական ընկերության նախագահ:

1890 թվականին Հիլուդը սխալ գտավ Կեմպեի ապացույցում: Նույն հոդվածում նա ապացուցեց հինգ գույնի թեորեմը՝ ցույց տալով, որ ցանկացած հարթ քարտեզ կարելի է ներկել ոչ ավելի, քան հինգ գույներով: Միևնույն ժամանակ, նա ապավինում էր Քեմփեի գաղափարներին: Հաջորդ դարում մեծ թվով տեսություններ մշակվեցին` փորձելով նվազեցնել գույների քանակը: Չորս գույնի թեորեմը վերջապես ապացուցվեց 1977 թվականին՝ Քենեթ Ապել և Վոլֆգանգ Հակեն գիտնականների կողմից, օգտագործելով համակարգչային թվարկում: Ապացույցի գաղափարը մեծապես ապավինում էր Հիլուդի և Քեմպեի գաղափարներին և անտեսեց միջանկյալ ուսումնասիրությունների մեծ մասը: Չորս գույնի թեորեմի ապացույցն առաջին ապացույցներից մեկն է, որում օգտագործվել է համակարգիչ:

912 թվականին Ջորջ Դեյվիդ Բիրխոֆը առաջարկել է օգտագործել քրոմատիկ թվեր, որը կարևոր մաս է գրաֆների հանրահաշվական տեսության մեջ, ուսումնասիրելու գունավորման խնդիրները: Քրոմատիկ թվերը հետագայում ընդհանրացվեց Ուիլյամ Թաթթի կողմից (Թաթթ բազմամոլ): Քեմփեն 1879 թվականին ուշադրություն է հրավիրել այն դեպքի վրա, երբ գրաֆիկը հարթ չէր: Բարձրագույն պատվերների մակերեսների վրա գրաֆների գունազարդման ընդհանրացումների բազմաթիվ արդյունքներ հայտնվեցին XX դարի սկզբին:

1960 թվականին Կլոդ Բուրգը ձևակերպեց կատարյալ գրաֆիկների վարկածը, որը հիմնավորված էր տեղեկատվական տեսության գաղափարից, մասնավորապես Շանոնի ներկայացրած գրաֆիկի կարողության զրոյական սխալից: Հայտարարությունը չհաստատված մնաց 40 տարի, մինչև չհաստատվեց որպես կատարյալ գրաֆների հայտնի կոշտ թեորեմ՝ մաթեմատիկոսներ Չուդնովսկայա, Րոբերտսոն , Թոմաս և Սեյմոուր՝ 2002 թվականին:

Գրաֆիկի ներկումը որպես ալգորիթմական խնդիր սկսեց ուսումնասիրվել 1970 թվականներից ի վեր։ Քրոմատիկ համարը որոշելը 21 NP- ի ամբողջական Կարպի խնդիրներից մեկն է (1972 թվական): Եվ միևնույն ժամանակ, տարբեր ալգորիթմներ մշակվել են այդ որոնման հիման վրա՝ Զյկովի վերադարձի և հետադարձման հեռացման և հետ կանչման միջոցով: 1981 թվականից ի վեր գրաֆիկական գունավորումն օգտագործվում է բաղադրիչների մեջ գրանցման բաշխման համար:

Սահմանում և տերմինաբանություն

Գագաթների գունավորում

Այս գրաֆը 3 գույներով կարող է գունավորվել12 եղանակով

Երբ մարդիկ խոսում են գրաֆները գունավորելու մասին, նրանք գրեթե միշտ նշանակում են գունավորել իրենց ուղղաթիռները, այսինքն՝ գրաֆիկի ուղղիչներին գագաթներին պիտակներ նշանակելը, որպեսզի ընդհանուր երկու կողերր ունենան տարբեր գույներ: Քանի որ հանգույցներով գրաֆիկները այս կերպ չեն կարող գունավորվել, դրանք քննարկման առարկա չեն:

Տերմինաբանությունը, որի պիտակները կոչվում են գույներ, գալիս է քաղաքական քարտեզների գունավորումից: Կարմիր կամ կապույտ գույնի գույներ օգտագործվում են միայն այն դեպքում, երբ գույների քանակը փոքր է, սովորաբար հասկացվում է, որ գույները ամբողջ թվեր են $\{1,2,3,...\}$։

G գրաֆի գագաթային $k$ -ներկում կոչվում է $a$:V(G)→ $\{1,...,k\}$ արտապատկերումը, իսկ 1,...,k թվերը կոչվում են գույներ ։ Գրաֆիկը գունավորելու համար անհրաժեշտ գույների ամենափոքր քանակը ${\displaystyle k}$-ն , որի դեպքում G-ն $k$ -ներկելի է կոչվում է G գրաֆի քրոմատիկ թիվ և հաճախ գրված է որպես $\chi (G)$։ Երբեմն օգտագործվում է $\gamma (G)$, քանի որ $\chi (G)$ նշում է Էյլերի բնութագիրը։ Մի գույնի միջոցով ընդգծված ուղղահայացների ենթաբազմությունը կոչվում է գունային դաս, յուրաքանչյուր այդպիսի դաս կազմում է անկախ հավաքակազմ: Այսպիսո , $k$-գունավորում դա նույնն է, այն էլ գագաթների բաժանումը $k$ անկախ հավաքածուների։

Գրոմով-Հաուսդորֆի հեռավորության տերմիններում քրոմատիկ թիվը

Կա G-կամայական գրաֆիկը բազմաթիվ  V  գագաթներով։ Վերցնենք երկու դրական իրական թվեր $a<b\leq 2a$ , և կքննարկենք $V$ ինչպես մետրային տարածք, որտեղ հարակից գագաթների միջև հեռավորությունը հավասար է $b$, մյուս բոլոր ոչ զրոյական հեռավորությունների հավասար են $a$։ Նշանակենք $a\Delta _{m}$ մետրային տար, բաղկացած $m$ կետերից, միմյանցից $a$ հեռավորության վրա։ Վերջապես, ցանկացած երկու մետրային տարածքների համար $X$ и $Y$, միջոցով $d_{GH}(X,Y)$ նշեք Գրոմով-Հաուսդորֆի հեռավորությունը միջև $X$ и $Y$։ Այնուհետև կստացվի հետևյալ արդյունքը՝

Թեորեմ (Ա. Հ. Իվանովը, Ա. Ա. Տուժիլին)։ Ամենամեծ դրական m ամբողջական համարն է, որի համար $d_{GH}(V,a\Delta _{m})=b$ (եթե նման բնական թվեր գոյություն չունեն, ապա մենք կդնենք $m=0$)։ Ապա$\chi (G)=m+1$։

• Քրոմատիկ թիվը $\chi (G)$հավասար է $1$, եթե $G$ գրաֆիկը չի պարունակում կողիկներ: Այս դեպքում հավասարությունը $d_{GH}(V,a\Delta _{m})=b$ ոչ մի m-ի համար չի կատարվել, հետևաբար, ձեռք բերված պայմանավորվածության համաձայն, $m=0$, տանելով դեպի հետևյալ հավասարության $\chi (G)=0+1=1$։
• Ըստ սահմանման, $\chi (G)$ չի գերազանցում $n$ քանակին շատ տարրեր $V$։ Մյուս կողմից, դժվար չէ ցույց տալ, որ $d_{GH}(V,a\Delta _{p})\leq \max\{a,\,b-a\}<b$ յուրաքանչյուր $p\geq n$, ուստի $m<n$ և նշանակում է $\chi (G)=m+1\leq n$։

Քրոմատիկ թվեր

Հիմնական հոդված՝ Хроматическое число § Хроматический многочлен

Քրոմատիկ բազմամոնիան ֆունկցիա է $P(G,t)$, որը հաշվում է գրաֆիկի t-գունանկարների քանակը $G$: Անունից հետևում է, որ տրված է $G$ այս հատկությունը բազմակողմանի է, կախված t։Այս փաստը հայտնաբերվել է Բիրկհոֆի և Լյուիսի կողմից `փորձելով ապացուցել չորս գույների վարկածը: Thumb | 3 vertices- ի բոլոր ոչ isomorphic գրաֆիկները և դրանց քրոմատիկ բազմամոլները: E3 դատարկ սյունը (կարմիր) թույլ է տալիս ներկել մեկ գույնով, մնացածը `ոչ: Օրինակ `կանաչ գրաֆիկը 12 եղանակով կարող է գունավորվել 3 գույներով: | 417x417px Օրինակ ՝ աջ կողմում գտնվող պատկերում պատկերված գրաֆիկը կարող է գունավորվել 12 եղանակով ՝ օգտագործելով 3 գույն: Երկու գույներով `այն սկզբունքորեն չի կարելի նկարել: Օգտագործելով 4 գույներ, մենք ստանում ենք 24 + 4 * 12 = 72 գունազարդման ընտրանքներ։ Բոլոր 4 գույներն օգտագործելիս կան 4: = 24 ճիշտ մեթոդ (4 կետի ցանկացած գրաֆիկի համար 4 գույների յուրաքանչյուր հանձնարարություն ճիշտ է); իսկ 4-ի յուրաքանչյուր 3 գույների համար գունազարդման 12 եղանակ կա: Այնուհետև, օրինակով գրաֆիկի համար, ճիշտ գունանկարների թվերի աղյուսակը կսկսվի այսպես.

Առկա գույներ	1	2	3	4	…
Գունազարդման եղանակների քանակը	0	0	12	72	…

Օրինակում գրաֆիկի համար, $P(G,t)=t(t-1)^{2}(t-2)$, և իհարկե, $P(G,4)=72$.

Քրոմատիկ բազմամոնիան առնվազն նույնքան տեղեկատվություն է պարունակում գունազարդման մասին $G$, որքան և քրոմատիկ համար։ Իսկապես, $\chi$ — ամենափոքր դրական ամբողջ թիվը, որը քրոմատիկ բազմամանդի արմատը չէ:

$\chi (G)=\min\{t\,\colon \,P(G,t)>0\}.$

Քրոմատիկ բազմապատկել որոշ գրաֆակներ

Եռանկյուն $K_{3}$	$t(t-1)(t-2)$
Ամբողջ գրաֆիկը $K_{n}$	$t(t-1)(t-2)\cdots (t-(n-1))$
Ծառ с $n$ կողեր	$t(t-1)^{n}$
ցիկլ $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
Պետերսենի ֆունկցիա	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)$

Եզրերի գունավորում

Հիմնական հոդված՝ Եզրերի գունավորում

Գրաֆիկի եզրային գունավորումը ենթադրում է գույների եզրեր տալ, որպեսզի միևնույն գույնի ոչ մի երկու եզր չմնա նույն ուղղահայաց: Այս առաջադրանքը համարժեք է դեմքերի շարքը անկախ դեմքերի խմբերի բաժանմանը: Գրաֆիկի եզրային գույնի համար պահանջվող գույների ամենափոքր քանակը $G$ — սա նրա քրոմատիկ ինդեքսն է, կամ ծայրամասային քրոմատիկ թիվը, $\chi '(G)$.

Ընդհանուր գունավորում

Հիմնական հոդված՝ Ընդհանուր գունավորում

Ընդհանուր գունավորումը գրաֆների ծայրամասերի և եզրերի գունազարդման տեսակներից մեկն է: Դա նշանակում է այնպիսի գունային հանձնարարություն, որ ոչ հարևան ուղղությունները, ոչ հարակից ծայրերը, և ոչ էլ դրանք միացնող ուղղություններն ու եզրերը ունեն նույն գույնը: Քրոմատիկ ընդհանուր թիվը $\chi ''(G)$ հաշվել $G$ — սա գույների ամենափոքր քանակն է, որն անհրաժեշտ է ցանկացած ամբողջական գույնի համար:

Հատկություններ

Քրոմատիկ հատկությունները

• Եթե $G$ — դատարկ գրաֆիկ,

$P(G,t)=1$

• Եթե ​​գրաֆիկ $G$ — տարբերվող ենթագրերի միավորում $H$ и $K$,

$P(G,t)=P(H,t)P(K,t)$

• Եթե կա $G$ հանգույց

$P(G,t)=0$

Քրոմատիկ թվի սահմանափակումները

• Տարբեր գույների բոլոր ուղղություններին վերագրելը միշտ տալիս է ճիշտ գունավորում, այնպես որ

$1\leq \chi (G)\leq n.$

• Միակ տեսակի գրաֆիկները, որոնք կարող են նկարել մեկ գույնով, զրոյական գրաֆներն են ։
• $K_{n}$ ամբողջ գրաֆիկը բաղկացած $n$ գագաթները պահանջում են $\chi (K_{n})=n$ գույներ։
• Օպտիմալ գունավորմամբ, պետք է լինի առնվազն մեկ եզր $m$ կողեր գրաֆիկի միջև յուրաքանչյուր երկու գունավոր դասերի, այնպես որ

$\chi (G)(\chi (G),1)\leq 2m.$

• Եթե $G$ հանդիսանում է չնախատեսված ենթածրագրերի միավորում $H$ и $K$, то

$\chi (G)=max\{\chi (H),\chi (K)\}$

• Եթե $G$պարունակում է սեղմակի չափ k, ապա անհրաժեշտ է նվազագույնը k սեղմման գունազարդման գույները, այլ կերպ ասած, քրոմատիկ թիվը ավելի մեծ է, կամ հավասար է սեղմման թվին:

$\chi (G)\geq \omega (G).$

Միջակայքային գրաֆների համար սա սահմանափակում է:

• Չորս գույնի թեորեմի համաձայն, ցանկացած հարթ գրաֆ կարող է գունավորվել չորս գույներով:
• 2 գունավոր գրաֆիկները երկկողմանի գրաֆներ են, ներառյալ ծառերը:

գրաֆ $G$ ին երկկողմանի է, եթե և միայն այն դեպքում, եթե այն չի պարունակում տարօրինակ երկարության ցիկլեր ։

• Ագահ գունազարդումը ցույց է տալիս, որ ցանկացած գրաֆիկ կարող է գունավորվել, երբ օգտագործվում է մեկ գույն ավելին, քան իր առավելագույն աստիճանի ուղղահայաց աստիճանը,

$\chi (G)\leq \Delta (G)+1.$

• Ամբողջ գրաֆիկները ունեն $\chi (G)=n$ и $\Delta (G)=n-1$, սյունակ-ցիկլեր $\chi (G)=3$ и $\Delta (G)=2$, ուստի նրանց համար այս սահմանափակումն ամենալավն է, մնացած բոլոր դեպքերում սահմանափակումները կարող են բարելավվել. Բրուքսի թեորեմը ասում է, որ

$\chi (G)\leq \Delta (G)$ կապակցված, պարզ հաշվարկի համար $G$, եթե $G$ ոչ ամբողջական գրաֆիկը, ոչ էլ գրաֆները ցիկլով։

Մեծ քրոմատիկ թվով սյունակներ

• Գրաֆիկները ունեն մեծ քրոմատիկ համարը, բայց հակառակ պնդումը միշտ չէ, որ ճիշտ է. Գրաֆիկը հնդկացորենի մի օրինակ է 4-գունավոր հաշվարկի առանց եռանկյունների, և այս օրինակը կարող է ամփոփվել է Միչենսկիի հաշվարկի։

թեորեմ (Ալեքսանդր Զիկով 1949, Յան Միխելսկի, 1955). Կան գրաֆիկներ, առանց եռանկյունների, կամայականորեն մեծ քրոմատիկ թվերով:

• Բրուքսի թեորեմից, մեծ քրոմատիկ համարով գրաֆիկները պետք է ունենան ուղղահայաց առավելագույն աստիճան: Տեղական մեկ այլ պայման, որի պատճառով քրոմատիկ քանակը կարող է մեծ լինել, մեծ կտավների առկայությունն է: Բայց գրաֆիկի գունավորումը կախված է ոչ միայն տեղական պայմաններից. Տեղական մեծ գերեզմանով գրաֆիկը տեղական տեսք ունի ծառի տեսքով, ուստի բոլոր ցիկլերը երկար են, բայց դրա քրոմատիկ թիվը հավասար չէ 2-ի:

Էրդշայի թեորեմ. Գոյություն ունեն գրաֆներ ՝ կամայականորեն մեծ գերեզմանով և քրոմատիկ համարով:

Քրոմատիկ ինդեքսի սահմանափակումները

• Եզրերի գունավորում $G$ —դա այն է, որ գունավորում տոպեր իր գծային գրաֆիկի $L(G)$։Այսինքն

$\chi '(G)=\chi (L(G)).$

• Ավելին,

Կոենիգի թեորեմ: $\chi '(G)=\Delta (G)$, եթե $G$ — երկդիմի։

• Ընդհանուր դեպքում, կապը շատ ավելի ուժեղ է, քան Բրուքսի թեորեմը ` ուղղահայաց գունավորումը տալիս է.

Վիզինգի թեորեմ. վերին առավելագույն աստիճանի գրաֆիկը՝ $\Delta$-ն ունի կողային քրոմատիկ թիվ $\Delta$ կամ $\Delta +1$.

Այլ հատկություններ

• Գրաֆիկը k- քրոմատիկ է, եթե և միայն այն դեպքում, եթե այն ունի ացիկլային ուղղվածություն, որի համար ամենաերկար ուղու երկարությունը k է: Դա ապացուցվեց Gallai - Hasse - Roy - Vitawer թեորեմում:
• Համար հարթ գրաֆիկները, գունավորում բարձունքների համարժեք ոչ մի տեղ չի զրոյական արդյունավետության հոսքի.
• Անսահման գրաֆիկների մասին, շատ ավելի քիչ բան է հայտնի: Ստորև բերված են անսահման գրաֆիկների գունազարդման երկու արդյունք:

1. Եթե անվերջ վանդակի բոլոր վերջնական ենթատեսակները $G$ k- քրոմատիկто և $G$ նաև k-քրոմատիկ է (ապացուցված է ընտրության աքսիոմի ենթադրությամբ): Սա Դե Բրյուենի - Էրդոսի թեորեմի հայտարարությունն է ։
2. Եթե ​​գրաֆիկը ընդունում է ամբողջական n- գունավորում որևէ մեկի համար $n\geqslant n_{0}$, ապա դա ընդունում է անվերջ լիարժեք գունավորում:

Բաց հարցեր

Օդանավի քրոմատիկ համարը, որում երկու կետերը հարակից են, եթե դրանց միջև կա միավոր հեռավորություն, անհայտ է: Այն կարող է լինել 5, 6, կամ 7։ Գրաֆիկների քրոմատիկ թվաքանակի վերաբերյալ այլ բաց հարցերը ներառում են Hadwiger ենթադրությունը, որում ասվում է, որ k- ի քրոմատիկ համարով ցանկացած գրաֆիկ ունի k կետերի ամբողջական գրաֆիկը, ինչպես իր անչափահասը, Էրդշան-Ֆաբեր-Լովաս ենթադրությունը: , որը սահմանափակում է ամբողջական գրաֆիկների քրոմատիկական քանակը, որոնք ունեն յուրաքանչյուր ընդհանուր զույգ գրաֆիկի համար ճշգրիտ մեկ ընդհանուր եզրագիծ և Ալբերտսոնի ենթադրությունը, որ k-chromatic գրաֆիկների շարքում լրիվ լրացված են այն խաչմերուկների ամենաքիչը քանակը:

Երբ Բիրկովն ու Լուիսը ներկայացրեցին քրոմատիկ բազմամիլիան ՝ չորս գույնի թեորեմը լուծելու փորձի մեջ, նրանք պնդում էին, որ գծային գրաֆների համար$G$ բազմապատկել $P(G,t)$այս միջակայքում չունի $[4,\infty )$։ Չնայած հայտնի է, որ նման քրոմատիկ բազմամոնիան տարածաշրջանում զրո չունի $[5,\infty )$, и что $P(G,4)\neq 0$, նրանց հայտարարությունը մնում է չհաստատված: Հարցը մնում է նաև բաց, թե ինչպես կարելի է տարբերակել գրաֆիկները նույն քրոմատիկ բազմամոլիկով և ինչպես որոշել, որ բազմամոլը քրոմատիկ է:

Գունազարդման ալգորիթմներ

Բազմահավաք ալգորիթմներ

Երկկողմ գրաֆիկի համար գունազարդման առաջադրանքը հաշվարկվում է գծային ժամանակով ՝ օգտագործելով առաջին լայնության որոնումը: Կատարյալ գրաֆների դեպքում քրոմատիկ համարը և դրա համապատասխան գունազարդումը կարելի է գտնել բազմամյա ժամանակով ՝ օգտագործելով կիսատագրված ծրագրավորում: Քրոմատիկ համարը գտնելու ճշգրիտ բանաձևերը հայտնի են գրաֆիկների շատ դասերի համար (անտառներ, ցիկլեր, անիվներ, ակորդային գրաֆներ) և կարող են հաշվարկվել նաև բազմամյա ժամանակով:

Ճշգրիտ ալգորիթմներ

K- ներկման դեպքի սպառիչ որոնման ալգորիթմը հաշվի է առնում բոլոր $k^{n}$ համադրությունը դասավորվածության գույների վանդակում հետ n գագաթներով և ստուգում է նրանց ճշգրտությունը։ Քրոմատիկ համարը և քրոմատիկ պոլիոմը հաշվարկելու համար այս ալգորիթմը հաշվի է առնում յուրաքանչյուր k–ն 1-ից մինչև n: Գործնականում նման ալգորիթմը կարող է կիրառվել միայն փոքր գրաֆիկների համար:

Օգտագործելով դինամիկ ծրագրավորում և գնահատելով ամենամեծ անկախ հավաքածուի չափը, գրաֆիկում k- ներկման հնարավորությունը կարող է ժամանակին լուծվել $O(2,445^{n})$։ Հայտնի են ավելի արագ ալգորիթմներ 3-և 4-գունազարդումներ, որոնք աշխատում են $O(1,3289^{n})$ և $O(1,7272^{n})$ ընթացքում։

Ծգում

Գագաթների ձգում — սա գործողություն է, որը գրաֆից $G$–ից կազմում է գրաֆիկ $G/uv$, նույնացնելով գագաթները $u$ и $v$, դրանք միացնող եզրերը հեռացնելով, և փոխարինելով $w$ ուղղահայացով, ուղղվում են կողորը գագաթով $u$ и $v$։ Այս գործողությունը կարևոր դեր է խաղում գրաֆի գունավորման վերլուծության մեջ:

Քրոմատիկ թիվը բավարարում է ռեկուրենտային հարաբերակցությանը:

$\chi (G)=min\{\chi (G+uv),\chi (G/uv)\}$,

որտեղ $u$–ն և $v$–ն ոչ հարակից գագաթներ են , $G+uv$ գրաֆիկ `ավելացված $uv$ կողերով Պ։ Որոշ ալգորիթմներ հիմնված են այդ համամասնության վրա ՝ արդյունքում արտադրելով ծառ, երբեմն կոչվում է նաև Զիկովի ծառ: Կատարման ժամանակը կախված $u$ և $v$ է գագաթների ընտրության մեթոդից ։

Քրոմատիկ բազմամոնիան բավարարում է կրկնվող հարաբերությունը.

$P(G-uv,t)=P(G/uv,t)+P(G,t)$,

որտեղ $u$–ն և $v$–ն հարակից գագաթներ են, $G-uv$ կողերի հեռացման գրաֆիկ ։ $P(G-uv,t)$ ներկայացնում է գրաֆիկի հնարավոր ճիշտ գունազարդումների թիվը , երբ $u$–ն և $v$ – ն կարող են ունենալ տարբեր գույներ։ Եթե $u$–ն и $v$–ն ունեն տարբեր գույներ, ապա մենք կարող ենք դիտարկել գրաֆիկը, որտեղ $u$–ն և $v$–ն հարակից են։ Եթե $u$–ն և $v$–ն ունեն նույն գույները, մենք կարող ենք դիտարկել գրաֆիկ, որտեղ $u$–ն և $v$–ն հարակից են։

Վերոհիշյալ տրված արտահայտությունները հանգեցնում են հետադարձման ընթացակարգին, որը կոչվում է հեռացման ալգորիթմ, որը հիմք է հանդիսացել գրաֆիկական գունազարդման շատ ալգորիթմների համար: Աշխատանքային ժամանակը բավարարում է նույն ռեկուրենտային հարաբերակցության, ինչպես նաև Ֆիբոնաչիի թվի, այնպես որ վատագույն դեպքում ալգորիթմը կաշխատի $((1+{\sqrt {5}})/2)^{n+m}=O(1,6180^{n+m})$ ընթացքում n և m գագաթների համար։ Գործնականում մասնաճյուղային և պարտադիր եղանակը և իզոմորֆային գրաֆները անտեսելը խուսափում են որոշակի հետադարձ զանգերից։ Գործառնական ժամանակը կախված է զույգ ուղղահայաց ընտրելու մեթոդից:

Ագահ գունավորում

Ալգորիթմի աշխատանքի ընթացքում կա երկու արդյունք՝ գագաթների տարբեր կարգերի ընտրության ժամանակ :Ա լգորիթմը կազմակերպում է գագաթները $v_{1}$,…,$v_{n}$ և հաջորդականորեն վերագրում է ուղղահայաց $v_{i}$–ին ամենափոքր հասանելի գույնը , հարև անների ներկման համար չօգտագործվող $v_{i}$ շարքում $v_{1}$,…,$v_{i-1}$,կամ ավելացնում է նորը: Արդյունքում գունազարդման որակը կախված է ընտրված կարգից: Միշտ կա այդպիսի պատվեր, որը ալգորիթմը տանում է դեպի գույների օպտիմալ $\chi (G)$ քանակ:Մյուս կողմից, ագահ ալգորիթմը կարող է լինել որքան վատ, օրինակ, թագը n գագաթներով կարող է նկարել 2 գույներով, բայց կա գագաթնակետների կարգը, որը հանգեցնում է ագահ գունավորում $n/2$ գույներով։

Ակորդային գրաֆիկի համար և նրա հատուկ դեպքերի համար (օրինակ ՝ ընդմիջման գրաֆ), ագահ գունազարդման ալգորիթմը կարող է օգտագործվել բազմամուսնական ժամանակում օպտիմալ գունավորում գտնելու համար ՝ ընտրելով ուղղահայացների կարգը հակադարձ բացառության կատարյալ կարգին: Այս ալգորիթմը կարող է կիրառվել գրաֆիկների ավելի լայն դասի (կատարյալ կարգավորված գրաֆիկների) վրա, այնուամենայնիվ, նման գրաֆիկների համար նման պատվեր գտնելը NP- բարդ խնդիր է:

Եթե ​​ուղղահայացները պատվիրված են ըստ իրենց աստիճանների, ագահ գունազարդման ալգորիթմը օգտագործում է ոչ ավելին, քան $max_{i}min\{d(v_{i})+1,i\}$ գույներ ,որ առավելագույնը 1-ով ավելի մեծ է , քան $\Delta$ (здесь $d(v_{i})$ — վերին աստիճան $v_{i}$). Այս ​​ալգորիթմը երբեմն կոչվում է ՈՒելշա–Պաուելիի ալգորիթմ ։ Մեկ այլ ալգորիթմի կարգը դինամիկ է սահմանում ՝ ընտրելով մեկի հաջորդ ուղղահայացը, որն ունի տարբեր գույների հարակից ուղղահայացների ամենամեծ քանակը: Գրաֆիկի գունազարդման շատ այլ ալգորիթմներ հիմնված են ագահ գունազարդման վրա և օգտագործել ստատիկ կամ դինամիկ ռազմավարություններ ՝ ուղղահայացների կարգը ընտրելու համար:

Զուգահեռ և բաշխված ալգորիթմներ

Բաշխված ալգորիթմների ոլորտում նմանատիպ խնդիր է առաջացել: Ենթադրենք, որ գրաֆիկի ուղղությունները համակարգիչներ են, որոնք կարող են միմյանց հետ շփվել, եթե դրանք միացված են մի կողմով: Խնդիրն է յուրաքանչյուր համակարգչի համար ընտրել իր համար «գույն», որպեսզի հարևան համակարգիչները ընտրեն տարբեր գույներ: Այս խնդիրը սերտորեն կապված է սիմետրիայի կոտրման խնդրի հետ: Առավել զարգացած հավանականական ալգորիթմները ավելի արագ են աշխատում, քան դետերմինիստական ​​ալգորիթմները ուղղանկյունների բավարար չափով մեծ առավելագույն աստիճանի գրաֆների համար ։ Հնարավոր արագ ալգորիթմներն օգտագործում են բազմակի փորձի տեխնիկան:

Սիմետրիկ գրաֆիկներում դետերմինիստական ​​բաշխված ալգորիթմները չեն կարողանում գտնել օպտիմալ եզրային գունավորումը: Համաչափությունից խուսափելու համար անհրաժեշտ է ավելի շատ տեղեկատվություն: Ստանդարտ ենթադրություն է արվում, որ ի սկզբանե յուրաքանչյուր եզրագիծ ունի յուրահատուկ նույնականացում, օրինակ ՝ այս $\{1,2,...,N\}$ շարքից ։ Այլ կերպ ասած, ենթադրվում է, որ մեզ տրվում է n- երանգավորում: Մարտահրավերն այն է, որ նվազեցնել գույների քանակը n -ից, օրինակ ՝ $(\Delta +1)$։ Որքան շատ գույներ են օգտագործվում (օրինակ, $O(\Delta )$ միասին $(\Delta +1)$), այնքան քիչ հաղորդագրություններ է անհրաժեշտ փոխանակել։

Բաշխված ագահ ալգորիթմի պարզ տարբերակ $(\Delta +1)$ -գունավորում պահանջում $\Theta (n)$ գուցե հարկ լինի ցանցի մի ծայրից մյուսը անցնել:

Ամենապարզ հետաքրքիր դեպքը n- ցիկլն է: Ռիչարդ Քոուլը և Ուզի Վիշկինը ցույց տվեցին, որ գոյություն ունի բաշխված ալգորիթմ, որը նվազեցնում է գույների քանակը n-ից մինչև $O(log(n))$, օգտագործելով միայն մեկ անգամ հարևանների միջև հաղորդագրություններ: Կրկնելով նույն ընթացակարգը, մենք կարող ենք ձեռք բերել n-ցիկլի 3-երանգավորում մինչև $O(log^{*}(n))$ կապի փուլեր (պայմանով, որ տրվեն եզակի հանգույցների նույնականացուցիչներ):

Լոգարիթմական ֆունկցիա $log^{*}$,Կրկնվող լոգարիթմը չափազանց դանդաղ աճող գործառույթ է ՝ «գրեթե կայուն»:Հետևաբար, Քոուլի և Վիշկինի արդյունքները բարձրացնում են այն հարցը, արդյոք կա n-ցիկլի բաշխված 3-գունավոր ալգորիթմ, որն ընթանում է անընդհատ ժամանակով: Nathan Lineal- ը ցույց տվեց, որ դա անհնար է. Ցանկացած որոշիչ բաշխված ալգորիթմ $\Omega (log^{*}(n))$ պահանջում է կապի փուլերը `n- ցիկլում N- գունավորումը 3-գունավորումը նվազեցնելու համար:

Քոուլի և Վիշկինի տեխնիկան կարող է կիրառվել նաև ուղղաձիգ սահմանափակ աստիճանի կամայական գրաֆիկի վրա, որի դեպքում գործարկման ժամանակը $P(\Delta )+O(log^{*}(n))$ է։ Այս մեթոդը ընդհանրացվել է միավորի օղակների գրաֆում Շնայդերի և այլոց կողմից:

Կողերի գունազարդման խնդիրը նույնպես ուսումնասիրվել է բաշխված մոդելի մեջ: Պենսոնցին և Ռիզզին հասան $(2\Delta -1)$-գունազարդում մինչև $O(\Delta +log^{*}(n))$ մինչև այս մոդել։ Ստորին սահմանը բաշխված գունավոր գագաթների համար, որը ձեռք է բերվել գծի կողմից, նույնպես կիրառելի է բաշխված կողոսկրերի գունազարդման խնդրի համար:

Ապակենտրոնացված ալգորիթմներ

Ապակենտրոնացված ալգորիթմները դրանք են, որոնցում ներքին հաղորդագրությունները թույլ չեն տալիս (ի տարբերություն բաշխված ալգորիթմների, որտեղ գործընթացները փոխանակում են տվյալները միմյանց հետ): Կան արդյունավետ ապակենտրոնացված ալգորիթմներ, որոնք հաջողությամբ հաղթահարում են գրաֆիկների գունավորման խնդիրը: Այս ալգորիթմները գործում են այն ենթադրության համաձայն, որ մի եզրագիծ ունակ է «զգալ», որ իր հարևան ուղղահայաց նկարները ներկված են նույն գույնի պես: Այլ կերպ ասած, հնարավոր է որոշել տեղական հակամարտություն: Այս պայմանը հաճախ բավարարվում է իրական ծրագրերում. Օրինակ, անլար ալիքով տվյալներ փոխանցելիս, փոխանցող կայանը, որպես կանոն, հնարավորություն ունի հայտնաբերելու, որ մեկ այլ կայան փորձում է միաժամանակ փոխանցել նույն ալիքին: Նման տեղեկատվություն ստանալու հնարավորությունը բավարար է, որպեսզի ալգորիթմները, որոնք հիմնված են սովորելու ավտոմատների վրա, մեկի հավանականությամբ, ճիշտ լուծում են գրաֆի գունավորման խնդիրը:

Հաշվողական բարդություն

Գրաֆիկը ներկելը հաշվարկայինորեն դժվար է: Պարզելու համար, արդյոք գրաֆիկը ընդունում է, որ տվյալ k- ի գունավորումը NP- ի ամբողջական խնդիր է, բացառությամբ k = 1 և k = 2. դեպքերի: Մասնավորապես, քրոմատիկ համարը հաշվարկելու խնդիրն NP- բարդ է: 3-երանգավորման խնդիրը NP- ամբողջական է նույնիսկ 4-րդ աստիճանի գծային գրաֆի դեպքում:

Նաև NP դժվար խնդիր է 4 գույներով գունավոր գրաֆիկի ներկումը 4 գույներով և k- գունավոր գրաֆիկը $k^{log(k)/25}$ բավական k մեծ արժեքների։

Քրոմատիկ բազմամյակի # P- դժվարության գործակիցների հաշվարկ: Ապացուցված է, որ չկա որևէ FPRAS ալգորիթմ ՝ ցանկացած ռացիոնալ համարի համար քրոմատիկ բազմագույնը հաշվարկելու համար k ≥ 1,5, բացի k = 2,եթե միայն չկատարվի, երբ NP = RP։

Դիմում

Պլանավորում

Գունավորում Տոպեր գունազարդման մոդելները պլանավորում են բազմաթիվ խնդիրներ: Իր ամենապարզ ձևակերպմամբ ՝ աշխատատեղերի որոշակի շարք պետք է բաշխվեն ժամանակի ընթացքում, յուրաքանչյուր այդպիսի աշխատանք տանում է մեկ հատված: Դրանք կարող են իրականացվել ցանկացած կարգով, բայց երկու աշխատանքները կարող են բախվել այն իմաստով, որ դրանք չեն կարող կատարվել միևնույն ժամանակ, քանի որ, օրինակ, նրանք օգտագործում են ընդհանուր ռեսուրսներ: Համապատասխան գրաֆիկը պարունակում է եզրագիծ յուրաքանչյուր աշխատատեղի համար և յուրաքանչյուր հակամարտող զույգի համար եզր: Կառուցված գրաֆիկի քրոմատիկական թիվը կատարման համար նվազագույն ժամանակն է առանց կոնֆլիկտի բոլոր աշխատանքների:

Պլանավորման խնդրի մանրամասները որոշում են գրաֆի կառուցվածքը: Օրինակ, երբ կա օդանավերի բաշխում ըստ թռիչքների, արդյունքում առաջացող կոնֆլիկտային գրաֆիկը ինտերվալային գրաֆիկ է, որպեսզի ներկման խնդիրը հնարավոր լինի արդյունավետ լուծել: Ռադիոհաճախականությունները բաշխելիս ձեռք է բերվում կոնֆլիկտների միավորի շրջանակների գրաֆ, և նման խնդրի համար կա 3-մոտեցման ալգորիթմ

Ռեգիստրների բաշխում

Կոմպիլյատորը համակարգչային ծրագիր է, որը թարգմանում է մեկ համակարգչային լեզու մյուսը: Արդյունավետ կոդի կատարման ժամանակը բարելավելու համար կոմպիլյատորի օպտիմալացման տեխնիկաներից մեկը գրանցումների բաշխումն է, որտեղ կոմպիլացվող ծրագրի առավել հաճախ օգտագործվող փոփոխականները պահվում են պրոցեսորի արագ գործող ռեգիստրներում: Իդեալական դեպքում փոփոխականները պահվում են գրանցամատյաններում, այնպես, որ դրանք բոլորը գտնվում են գրանցամատյաններում դրանց օգտագործման ժամանակ:

Ստանդարտ մոտեցումը այս խնդրին է նկատի ունենալ, որ խնդիրը գունավորում գրաֆների. Կոմպիլյատորը կառուցում է ինտերֆերենցիոն գրաֆիկը, որտեղ գագաթները համապատասխանում են փոփոխականներին, իսկ եզրը կապում է դրանցից երկուսը, եթե դրանք անհրաժեշտ են ժամանակի միևնույն կետում: Եթե այս գրաֆիկը k-քրոմատիկ է, ապա փոփոխականները կարող են պահվել k ռեգիստրներում։

Թվային ջրանիշներ

Թվային ջրային նշանների տեխնոլոգիա (անգլ. ՝ ՝ digital watermarking) թույլ է տալիս տվյալների հետ միասին (լինի դա մեդիաֆայլեր, գործարկվող ֆայլեր և այլն) փոխանցել ինչ-որ թաքնված հաղորդագրություն ("ջրի մակարդակի նշագիծ", Watermark) ։ Նման թաքնված հաղորդագրությունը կարող է կիրառվել հեղինակային իրավունքի պաշտպանության բացահայտել տվյալների սեփականատիրոջը.

Սա կարևոր է, օրինակ, հաստատել աղբյուրը դրանց տարածման անօրինական ճանապարհով. Կամ հաստատել իրավունքները տվյալների, օրինակ, ծրագրային համակարգերի վրա բյուրեղյա (system-on-chi

Հաղորդագրությունը կարող է կոդավորված, այդ թվում՝ ձևով բաշխման ռեգիստրների. Առաջարկվեց այս տեխնիկայից մեկը Qu и Potkonjak (հետևաբար, այն երբեմն կոչվում է QP ալգորիթմ).

Այն բաղկացած է հետևյալից.թող $G$ — (անհամատեղելիության գրաֆիկ) պրոցեսորի գրանցման հատկացում , որի մասին խոսվել է վերը։ Դրա գունավորումը օգտագործվում է ծրագրում - ավելին, այն օգտագործվում է այնպես, որ թույլատրելի է գրաֆիկի պարունակությունը փոխել իր քրոմատիկ համարի մի փոքր աճով: Ստացվում է, որ հնարավոր է հաղորդագրություն կոդավորել ծրագրային արտադրանքի մեջ ՝ օգտագործելով գրաֆիկի ներկ $G$, այսինքն, բաշխման ռեգիստրների։

Դուք կարող եք ստանալ այս հաղորդագրությունը համեմատելով ռեգիստրների բաշխումը սկզբնական գունազարդման հետ; Կան նաև եղանակներ համոզվելու համար, թե արդյոք որևէ հաղորդագրություն կոդավորված է ծրագրում, առանց նախնական օգտագործման:

Հետագայում տարբեր հեղինակներ զարգացրել և հստակեցրել են գաղափարները Qu և Potkonjak.

Այլ ծրագրեր

Գրաֆների գունազարդման խնդիրը դրվել է կիրառման բազմաթիվ այլ ոլորտներում, ներառյալ նմուշային համադրումը:

Sudoku հանելուկ լուծումը կարող է դիտվել որպես ավարտելով գունավորում 9 գույներով սահմանված գրաֆիկի 81 գագաթներով։

Գրականություն

• Донец, Г. А.; Шор, Н. З. (1982), Алгебраический подход к проблеме раскраски плоских графов, Наукова думка, էջեր 5–7
• Зыков, А. А. (1949), «О некоторых свойствах линейных комплексов», Матем. сб., 24(66) (2): 163–188
• Beigel, R.; Eppstein, D. (2005), «3-coloring in time O(1.3289ⁿ)», Journal of Algorithms (English), 54 (2)): 168–204, doi:10.1016/j.jalgor.2004.06.008{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Birkhoff, G. D.; Lewis, D. C. (1946), «Chromatic Polynomials» (PDF), Trans. Amer. Math. Soc. (English), 60: 355–451{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Brélaz, D. (1979), «New methods to color the vertices of a graph», Communications of the ACM (English), 22 (4): 251–256, doi:10.1145/359094.359101{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Brooks, R. L.; Tutte, W. T. (1941), «On colouring the nodes of a network», Proceedings of the Cambridge Philosophical Society (English), 37 (2): 194–197, doi:10.1017/S030500410002168X{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• N. G. de Bruijn, P. Erdős A colour problem for infinite graphs and a problem in the theory of relations (English) // Nederl. Akad. Wetensch. Proc. Ser. A. — 1951. — Т. 54. — С. 371—373. (= Indag. Math. 13)
• Byskov, J.M. (2004), «Enumerating maximal independent sets with applications to graph colouring», Operations Research Letters (English), 32 (6): 547–556, doi:10.1016/j.orl.2004.03.002{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Cormen, T. H.; Leiserson, C. E.; Rivest, R. L. (1990), Introduction to Algorithms (1st ed.), The MIT Press
• Collberg, Christian; Thomborson, Clark; Townsend, Gregg M. (2004), Dynamic Graph-Based Software Watermarking (PDF)
• Chaitin, G. J. (1982), «Register allocation & spilling via graph colouring», Proc. 1982 SIGPLAN Symposium on Compiler Construction (English), էջեր 98–105, doi:10.1145/800230.806984, ISBN 0-89791-074-5{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Cole, R.; Vishkin, U. (1986), «Deterministic coin tossing with applications to optimal parallel list ranking», Information and Control (English), 70 (1): 32–53, doi:10.1016/S0019-9958(86)80023-7{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Dailey, D. P. (1980), «Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete», Discrete Mathematics (journal) (English), 30 (3): 289–293, doi:10.1016/0012-365X(80)90236-8 {{citation}}: Text "Discrete Mathematics" ignored (օգնություն)CS1 սպաս․ չճանաչված լեզու (link)
• Diestel, R. (2005), Graph theory (PDF) (English){{citation}}: CS1 սպաս․ չճանաչված լեզու (link) Արխիվացված է Նոյեմբեր 25, 2014 Wayback Machine-ի միջոցով:
• Duffy, K.; O'Connell, N.; Sapozhnikov, A. (2008), «Complexity analysis of a decentralised graph colouring algorithm» (PDF), Information Processing Letters (English), 107: 60–63, doi:10.1016/j.ipl.2008.01.002{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Fawcett, B. W. (1978), «On infinite full colourings of graphs», Canadian Journal of Mathematics (English), XXX: 455–457 {{citation}}: Text "Can. J. Math." ignored (օգնություն)CS1 սպաս․ չճանաչված լեզու (link)
• Fomin, F.V.; Gaspers, S.; Saurabh, S. (2007), «Improved Exact Algorithms for Counting 3- and 4-Colorings», Proc. 13th Annual International Conference, COCOON 2007, Lecture Notes in Computer Science (English), vol. 4598, Springer, էջեր 65–74, doi:10.1007/978-3-540-73545-8_9, ISBN 978-3-540-73544-1{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Garey, M. R.; Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness (English), W.H. Freeman, ISBN 0-7167-1045-5{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), «Some simplified NP-complete problems», Proceedings of the Sixth Annual ACM Symposium on Theory of Computing (English), էջեր 47–63, doi:10.1145/800119.803884{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Goldberg, L. A.; Jerrum, M. (July 2008), «Inapproximability of the Tutte polynomial», Information and Computation, 206 (7): 908–929, doi:10.1016/j.ic.2008.04.003
• Goldberg, A. V.; Plotkin, S. A.; Shannon, G. E. (1988), «Parallel symmetry-breaking in sparse graphs», SIAM Journal on Discrete Mathematics, 1 (4): 434–446, doi:10.1137/0401044
• Guruswami, V.; Khanna, S. (2000), «On the hardness of 4-coloring a 3-colorable graph», Proceedings of the 15th Annual IEEE Conference on Computational Complexity (English), էջեր 188–197, doi:10.1109/CCC.2000.856749, ISBN 0-7695-0674-7{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Jaeger, F.; Vertigan, D. L.; Welsh, D. J. A. (1990), «On the computational complexity of the Jones and Tutte polynomials», Mathematical Proceedings of the Cambridge Philosophical Society (English), 108: 35–53, doi:10.1017/S0305004100068936{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Jensen, Tommy R.; Toft, Bjarne (1995), Graph Coloring Problems (English), John Wiley & Sons, ISBN 0-471-02865-7 {{citation}}: Unknown parameter |isbn2= ignored (օգնություն)CS1 սպաս․ չճանաչված լեզու (link)
• Khot, S. (2001), «Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring», Proc. 42nd Annual Symposium on Foundations of Computer Science (English), էջեր 600–609, doi:10.1109/SFCS.2001.959936, ISBN 0-7695-1116-3{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Kubale, M. (2004), Graph Colorings (English), American Mathematical Society, ISBN 0-8218-3458-4{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Kuhn, F. (2009), «Weak graph colorings: distributed algorithms and applications», Proceedings of the 21st Symposium on Parallelism in Algorithms and Architectures (English), էջեր 138–144, doi:10.1145/1583991.1584032, ISBN 978-1-60558-606-9{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Lawler, E.L. (1976), «A note on the complexity of the chromatic number problem», Information Processing Letters (English), 5 (3): 66–67, doi:10.1016/0020-0190(76)90065-X{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Leith, D.J.; Clifford, P. (2006), «A Self-Managed Distributed Channel Selection Algorithm for WLAN», Proc. RAWNET 2006, Boston, MA (PDF) (English){{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Linial, N. (1992), «Locality in distributed graph algorithms», SIAM Journal on Computing (English), 21 (1): 193–201, doi:10.1137/0221015{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• van Lint, J. H.; Wilson, R. M. (2001), A Course in Combinatorics (2nd ed.), Cambridge University Press, ISBN 0-521-80340-3
• Molloy, Michael; Reed, Bruce (2002), Graph colouring and the probabilistic method (English), Springer, ISBN 3-540-42139-4, ISSN 0937-5511{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Marx, Dániel (2004), «Graph colouring problems and their applications in scheduling», Periodica Polytechnica, Electrical Engineering (English), vol. 48, էջեր 11–16, CiteSeerX:10.1.1.95.4268{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Mycielski, J. (1955), «Sur le coloriage des graphes» (PDF), Colloq. Math., 3: 161–162.
• Myles, Ginger; Collberg, Christian S. (2003), «Software Watermarking Through Register Allocation: Implementation, Analysis, and Attacks», ICISC, էջեր 274–293, doi:10.1007/b96249
• Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), «Theorem 3.13», Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, էջ 42, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058.
• Panconesi, Alessandro; Rizzi, Romeo (2001), «Some simple distributed algorithms for sparse networks», Distributed Computing (English), Berlin, New York: Springer-Verlag, 14 (2): 97–100, doi:10.1007/PL00008932, ISSN 0178-2770{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Panconesi, A.; Srinivasan, A. (1996), «On the complexity of distributed network decomposition», Journal of Algorithms (English), vol. 20{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Qu, Gang; Potkonjak, Miodrag (1998), «Analysis of watermarking techniques for graph coloring problem», ICCAD, էջեր 190–193, doi:10.1145/288548.288607
• Schneider, J. (2010), «A new technique for distributed symmetry breaking», Proceedings of the Symposium on Principles of Distributed Computing (PDF) (English), Արխիվացված է օրիգինալից (PDF) 2013-07-30-ին{{citation}}: CS1 սպաս․ չճանաչված լեզու (link) Արխիվացված է Հուլիս 30, 2013 Wayback Machine-ի միջոցով:
• Schneider, J. (2008), «A log-star distributed maximal independent set algorithm for growth-bounded graphs», Proceedings of the Symposium on Principles of Distributed Computing (PDF) (English), Արխիվացված է օրիգինալից (PDF) 2013-07-30-ին{{citation}}: CS1 սպաս․ չճանաչված լեզու (link) Արխիվացված է Հուլիս 30, 2013 Wayback Machine-ի միջոցով:
• Sekine, K.; Imai, H.; Tani, S. (1995), «Computing the Tutte polynomial of a graph of moderate size», Proc. 6th International Symposium on Algorithms and Computation (ISAAC 1995), Lecture Notes in Computer Science (English), vol. 1004, Springer, էջեր 224–233, doi:10.1007/BFb0015427, ISBN 3-540-60573-8{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Tutte, W. T. (1984), «Graph theory», Encyclopedia of mathematics and applications (English), Cambridge University Press, 21, ISBN 0-521-30241-2{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Welsh, D. J. A.; Powell, M. B. (1967), «An upper bound for the chromatic number of a graph and its application to timetabling problems», The Computer Journal, 10 (1): 85–86, doi:10.1093/comjnl/10.1.85
• Wilf, H. S. (1986), Algorithms and Complexity (English), Prentice–Hall{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
• Zhu, William; Thomborson, Clark (2006), «Recognition in software watermarking», MCPS '06: Proceedings of the 4th ACM international workshop on Contents protection and security, ACM, էջեր 29–36, doi:10.1145/1178766.1178776, ISBN 1-59593-499-5