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

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

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

Սահմանումներ և նշանակումներ

Դիցուք Φ-ն χ'(G)-կողային-ներկում է G գրաֆի և χ'(G)=Δ(G)+k (k≥1), r'_φ (G)=min(∑_j=1^k|Φ⁻¹ (i_j):

G գրաֆի համար սահմանենք ենթահատումների թիվ հետևյալ կերպ.

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

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

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

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

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

Լեմմա 1.2 Դիցուք e₁ և e₂ G գրաֆի մինիմալ գունային դասի երկու տարբեր կողեր են, ապա C_e1 և C_e2 ցիկլերը չեն հատվում։
Դեպք 1. Դիցուք e₁=v₁ω₁ ∈ H₁, ապա C_e1 ցիկլի կողերը ներկված են 3 և 2 գույներով։ Եթե

e₂ ∈ H₁, ապա C_e2 ցիկլի կողերը նույնպես ներկված են 3 և 2 գույներով։ Այսպիսով C_e1 և C_e2 ցիկլերի հարևան կողերը ներկված են 1-ով, հետևաբար ցիկլերը չեն կարող հատվել։
Դեպք 2. Եթե e₂ = v₂ω₂  !∈ H₁, ենթադրենք e₂ ∈ H₂, ապա C_e2-ի կողերը ներկված են 3-ով և 1-ով։ Ենթադրենք հակառակը՝ գոյություն ունի e ∈ E(C_e1) Λ E(C_e2) , պարզ է որ e₁ !∈ C_e2: Այսպիսով գոյություն ունի e ∈ E(C_e1) Λ E(C_e2): e₁-ից մինիմալ հեռավորությամբ ՝ ներկված 3-գույնով։ Եթե e կողը հարևան չէ e₂ –ին, ապա e₁ կողը կներկենք 2 կամ 3 գույներով և կփոխենք e₁ կողը e կողին միացնող կարճ ճանապարհի կողերի գույները՝ e-ն կներկենք 4-գույնով։ վերաներկումից հետո v₂ գագաթից դեպի ω₂ գագաթ (3, 1) ճանապարհ չի լինի, որը հակասում է 1.1 լեմմին[3]: Իսկ եթե e կողը հարևան է e₂-ին, ապա e-ն կներկենք 4-գույնով, e₂ կողը 3-գույնով և v₁-ից ω₁ (2, 3) ճանապարհ գոյություն չի ունենա, որը կրկին հակասում է լեմմ 1.1-ին[3]: Այսպիսով ապացուցվեվ, որ C_e1 և C_e2 ցիկլերը չեն հատվում։

Ստացված արդյունքից ուղակիորեն հետևում է թեորեմի պնդումը՝ 4-գույնով ներկված կողերի վրա կավելացնենեք մեկն գագաթ, որոնք կողերը կտրոհեն 2 կողերի։ Քանի որ գրաֆում e կողը մինիմալ ներկման ժամանակ ներկվել է 4-գույնով, ապա e £ H_i որտեղ i £ {1,2,3}: Առանց ընդհանրությունը չխախտելու կարելի է ենթադրել, որ ունենք հետևյալ տեսքը՝ դիցուք e=uv, քանի որ e £ H_i, ապա 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. 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. 473–482.
4. V. Mkrtchyan, E. Steffen, Measures of edge-uncolorability. Discrete Math. 312 (2012), pp. 476–478
5. Պ.Ա. Պետրոսյան, Վ.Վ. Մկրտչյան, Ռ.Ռ. Քամալյան, Գրաֆների տեսություն, ԵՊՀ. հրատ., Եր., 2015.
6. E. Steffen, Classifications and characterizations of snarks, Discrete Math. 188 (1998), pp. 183–203.
7. E. Steffen, Measurements of edge-uncolorability, Discrete Math. 280 (2004), pp. 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.