Ենթատրոհումներ խորանարդ գրաֆներում

Դիսկրետ մաթեմատիկայում մեծ ուշադրություն է հատկացվում ներկումների խնդիրների հետազոտություններին։ Դա պայմանավորված է ինչպես ներկումների խնդիրների մի շարք կարևոր կիրառական խնդիրների հետ առկա սերտ կապով, այնպես էլ նրանով, որ դիսկրետ մաթեմատիկայում առկա են բազմաթիվ խնդիրներ, որոնք կարելի է ձևակերպել որպես ներկումների խնդիրներ (ֆակտորիզացիայի խնդիրներ, տրոհման խնդիրներ, Ռամսեյի տեսության խնդիրներ և այլն)։ Մասնավորապես, նշանակալի փոխադարձ կապ կա կարգացուցակների տեսության խնդիրների և գրաֆների ներկումների խնդիրների միջև։ Օրինակ, քննաշրջանի օպտիմալ կարգացուցակ կառուցելու խնդիրը բերվում է գրաֆի քրոմատիկ թվի որոշմանը։ Գրաֆի քրոմատիկ դասը գտնելու խնդրին բերվում է սպորտային մրցումների կարգացուցակ կազմելու խնդիրը, իսկ երկկողմանի գրաֆների հատուկ տիպի կողային ներկումների խնդիրները բազմաթիվ աշխատանքներում ծառայել են որպես ուսումնական դասացուցակների գոյության, կառուցման և թվային պարամետրերի գնահատման հարցերի հետազոտման մոդելներ։

Ներկա աշխատանքում օգտագործված է գրաֆների տեսության ստանդարտ նշանակումները [5] Գրաֆների տեսություն և ներկայացված է գրաֆների ներկումների հետ կապված մի քանի պարամետրեր որոնք ցույց են տալիս թե գրաֆը որքանով է «հեռացված» 1-ին դասի գրաֆներից։ Այս աշխատանքը շարունակում է Վ. Մկրտչյանի և Է. Շտեֆենի ուսումնասիրությունները խորանարդ, պարզ և մուլտիգրաֆների քրոմատիկ դասի հետ կապված [3][4][6][7]: Գրաֆների դասակարգումը հիմնված է Վիզինգի հայտնի թեորեմի վրա [8], որը պնդում է, որ կամայական G պարզ գրաֆը կողային ներկելի է ∆(G) կամ ∆(G)+1 գույներով և համապատասխանաբար անվանվում 1-ին կամ 2-րդ դասի գրաֆներ։ 
Նշված հեղինակների կողմից մասնավորապես ապացուցվել է, որ խորանարդ և պարզ գրաֆների համար 1,2,...,Δ գույներով չներկվող կողերի քանակը նույն է ինչ գրաֆի կողերի քանակից հանենք մի հատուկ մաքսիմալ Δ-ներկելի ենթագրաֆի կողերի քանակը (re(G)=r'(G) ): Ներկա աշխատանքում հետազոտվել է գրաֆների կողային ներկումների հետ կապված մեկ այլ պարամետր՝ «ենթատրոհումների թիվ»
, որը սերտ կապված է նշված հեղինակների կողմից սահմանված պարամետրերի հետ։ Մասնավորապես խորանարդ գրաֆների դեպքում դրանք ուղակիորեն համընկնում են, ավելին, համընկնում են նաև մի քանի այլ նմանատիպ պարամետրերի հետ։
## Սահմանումներ և նշանակումներ
Դիցուք Φ-ն χ'(G)-կողային-ներկում է G գրաֆի և χ'(G)=Δ(G)+k (k≥1), r'φ (G)=min(∑j=1k|Φ−1 (ij): 
 G գրաֆի համար սահմանենք ենթահատումների թիվ հետևյալ կերպ.

re'(G)=minφr'φ(G):
re(G)-ով նշանակենք կողերի մինիմալ քանակը, որոնց հեռացնելիս կստացվի H ենթագրաֆ, որի համար χ'(H)=Δ(G), կամ որ նույնն է re(G)=|E(G)|-|E(H)|, որտեղ H-ը G գրաֆի մաքսիմալ Δ(G)-կողային-ներկելի ենթագրաֆն է։

Կասենք H-ը  G-ի   ենթատրոհումն է, եթե H-ը ստացվել է G-ից կիրառելով վերջավոր քանակի կողի տրոհում գործողություն։ Դիցուք f:E(G)→Z+  ֆունկցիա է որով որոշվում է թե քանի անգամ է e £ E(G) կողը տրոհվում և ստացվում Hf գրաֆը։ Սահմանենք G գրաֆի համար ենթատրոհումների թիվը հետևյալ կերպ.

sn(G)=minf{Σe £ E(G)f(G)|(Hf-ը G գրաֆի ենթատրոհումն է f-ի դեպքում և χ' (Hf )=∆(G)}:

***Ընդհանուր բնույթի արդյունքներ***
Այս աշխատանքում առանցքային նշանակություն ունի Վիզինգի թեորեմը. [8][9]:
*Թեորեմ 1.1.*  G գրաֆի համար Δ(G) ≤ χ՛(G) ≤ Δ(G) + µ(G), որտեղ µ(G)-ն կողերի մաքսիմալ պատիկությունն է։
Շտեֆենի կողմից ապացուցվել է հետևյալը.[6]

*Թեորեմ 1.2*  Ցանկացած G խորանարդ գրաֆի համար rv (G)=c(G):
Մեր կողմից ապացուցվել է հերևյալը
*Թեորեմ 1.1* G խորանարդ գրաֆի համար r՛e(G) = sn(G):
*Ապացույց.* Ապացույցը կատարելու համար ձևակերպենք հետևյալ լլեմման.

*Լեմմա 1.2*  Դիցուք e1 և e2 G գրաֆի մինիմալ գունային դասի երկու տարբեր կողեր են, ապա Ce1 և Ce2 ցիկլերը չեն հատվում։
*Դեպք 1.* Դիցուք  e1=v1ω1 ∈ H1, ապա Ce1 ցիկլի կողերը ներկված են 3 և 2 գույներով։ Եթե
 
e2 ∈ H1, ապա Ce2 ցիկլի կողերը նույնպես ներկված են 3 և 2 գույներով։ Այսպիսով Ce1 և Ce2 ցիկլերի հարևան կողերը ներկված են 1-ով, հետևաբար ցիկլերը չեն կարող հատվել։
*Դեպք 2.* Եթե e2  = v2ω2  !∈ H1, ենթադրենք e2 ∈ H2, ապա Ce2-ի կողերը ներկված են 3-ով և 1-ով։ Ենթադրենք հակառակը՝ գոյություն ունի e ∈ E(Ce1) Λ E(Ce2) , պարզ է որ  e1 !∈ Ce2: Այսպիսով գոյություն ունի e ∈ E(Ce1) Λ E(Ce2): e1-ից մինիմալ հեռավորությամբ ՝ ներկված 3-գույնով։ Եթե e կողը հարևան չէ e2 –ին, ապա e1 կողը կներկենք 2 կամ 3 գույներով և կփոխենք e1 կողը e կողին միացնող կարճ ճանապարհի կողերի գույները՝ e-ն կներկենք 4-գույնով։ վերաներկումից հետո v2 գագաթից դեպի ω2  գագաթ (3, 1) ճանապարհ չի լինի, որը հակասում է *1.1 լեմմին*[3]: Իսկ եթե e կողը հարևան է e2-ին, ապա e-ն կներկենք 4-գույնով, e2 կողը 3-գույնով և v1-ից ω1 (2, 3) ճանապարհ գոյություն չի ունենա, որը կրկին հակասում է *լեմմ 1.1*-ին[3]: Այսպիսով ապացուցվեվ, որ Ce1 և Ce2 ցիկլերը չեն հատվում։

Ստացված արդյունքից ուղակիորեն հետևում է թեորեմի պնդումը՝ 4-գույնով ներկված կողերի վրա կավելացնենեք մեկն գագաթ, որոնք կողերը կտրոհեն 2 կողերի։ Քանի որ գրաֆում e կողը մինիմալ ներկման ժամանակ ներկվել է 4-գույնով, ապա e £ Hi որտեղ i £ {1,2,3}: Առանց ընդհանրությունը չխախտելու կարելի է ենթադրել, որ ունենք հետևյալ տեսքը՝ դիցուք e=uv, քանի որ e £ Hi, ապա u և v գագաթների համար զբաղված է i-գույնը՝ 
i £ (c(V) Λ c(U)), ենթադրենք i=1, հետևաբար u և v գագաթներում 2 և 3 գույներն են մասնակցում և ունեն հետևյալ պատկերի նկատմամբ սիմետրիկ տեսք.Տվյալ դեպքում ավելացված ν գագաթը հնարավորություն է տալիս (v,ν) կողը ներկել 3-գույնով, իսկ (ν,u) կողը՝ 2-գույնով։ Այսպիսով ստացանք որ
sn(G) ≤ r'e(G):
Մյուս կողմից ակնհայտ է որ
sn(G) ≥ r'e(G):
Քանի որ յուրաքանչյուր 4-գույնով ներկված կողի համար առնվազն մեկ գագաթ պետք է ավելացնել որպեսզի հնարավոր լինի այն ներկել ավելի փոքր գույներով։ Հետևաբար
sn(G) = r'e(G):

## Գրականություն
1. D. Aslanyan, V. Mkrtchyan, S. Petrosyan, G. Vardanyan, On disjoint matchings in cubic graphs: Maximum 2-edge-colorable and maximum 3-edge-colorable subgraphs, Discrete Applied Math. 172 (2014), pp.&nbsp;12–27 
2. G. Chartrand, P. Zhang, Chromatic Graph Theory, Chapman and Hall/CRC, 2009
3. V. Mkrtchyan, E. Steffen, Maximum Δ-edge-colorable subgraphs of class II graphs. Journal of Graph Theory 70 (2012), pp.&nbsp;473–482.
4. V. Mkrtchyan, E. Steffen,  Measures of edge-uncolorability. Discrete Math. 312 (2012), pp.&nbsp;476–478
5. Պ.Ա. Պետրոսյան, Վ.Վ. Մկրտչյան, Ռ.Ռ. Քամալյան, Գրաֆների տեսություն, ԵՊՀ. հրատ., Եր., 2015.
6. E. Steffen, Classifications and characterizations of snarks, Discrete Math. 188 (1998), pp.&nbsp;183–203.
7. E. Steffen, Measurements of edge-uncolorability, Discrete Math. 280 (2004), pp.&nbsp;191–214.
8. В.Г. Визинг, Об оценке хроматического класса р-графа, Дискретный анализ 3 (1964), стр. 25-30.
9. В.Г. Визинг, Хроматический класс мультиграфа, Кибернетика, N 3, (1965), стр. 29-39.
10. D.B. West, Introduction to Graph Theory, Prentice-Hall, New Jersey, 2001.

Կատեգորիա:Գրաֆների տեսություն