«Գրաֆների տեսություն»–ի խմբագրումների տարբերություն

Content deleted Content added
Պիտակներ՝ Խմբագրում բջջային սարքով Խմբագրում կայքի բջջային տարբերակից
Տող 57.
Ճիշտ գագաթային ներկումների հայտնի չլուծված խնդիրներից է [[Հադվիգերի հիպոթեզ]]ը, ըստ որի ''k'' քրոմատիկ թիվ ունեցող գրաֆը պետք է պարունակի ''k''-գագաթանի լրիվ գրաֆը որպես մինոր։ Այս հիպոթեզը չորս գույների թեորեմի ընդհանրացումն է։
 
==== վվվվվԿողայինԿողային ներկումներ ====
Երբ գագաթների փոխարեն ներկվում են կողերը և պահանջ է դրվում, որ կից կողերը ունենան տարբեր գույներ, այդպիսի ներկումը կոչվում է ''ճիշտ կողային ներկում'': Ճիշտ կողային ներկման դեպքում նվազագույն գույների քանակը կոչվում է գրաֆի [[քրոմատիկ դաս]], որը հաշվելը ևս NP-լրիվ խնդիր է։ [[Վիզինգի թեորեմ]]ի համաձայն, քրոմատիկ դասը կարող է հավասար լինել գրաֆի առավելագույն աստիճանին, կամ դրանից մեծ լինել ճիշտ մեկով։