Գրաֆների միջակայքային տոտալ ներկումներ

Ներածություն

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

Գրաֆների տոտալ ներկումները ներմուծվել են Վ. Վիզինգի և Մ. Բեհզադի [5] կողմից 60-ական թվականներին։ G գրաֆի տոտալ ներկումը դա այդ գրաֆի գագաթների և կողերի ներկում է, որի դեպքում հարևան գագաթները, կողերը և կից գագաթները և կողերը ներկվում են տարբեր գույներով։ G գրաֆի X"(G) տոտալ քրոմատիկ թվի տակ հասկանում են այն նվազագույն գույների քանակը, որն անհրաժեշտ է G գրաֆի տոտալ ներկման համար։ Նշենք նաև, որ [5,28]-ում առաջարկվել է հիպոթեզ, համաձայն որի X"(G) <= Delta(G) բոլոր գրաֆների համար, որտեղ Delta(G)-ն G գրաֆի գագաթների առավելագույն աստիճանն է։ Այս հիպոթեզն այժմ հայտնի է որպես Տոտալ Ներկումների Հիպոթեզ [11]։ Հայտնի է նաև, որ այն ճիշտ է լրիվ գրաֆների [6], երկկողմանի գրաֆների, լրիվ k-կողմանի գրաֆների, G հարթ գրաֆների, որոնց Delta(G) != [7, 8, 14, 25, 29], G գրաֆների, որոնց delta(G) >= 3 * |V(G)| / 4 [10], որտեղ delta(G)-ն G գրաֆի գագաթների նվազագույն աստիճանն է, և գրաֆների, որոնց առավելագույն աստիճանը բավականին փոքր է։ Մ. Ռոզենֆելդի [24] և Ն. Վիժայադիտյայի [27] կողմից ապացուցվել է, որ G գրաֆի տոտալ քրոմատիկ թիվը չի գերազանցում 5-ի, երբ delta(G) = 3։ Ա. Կոստոչկան [12, 13] աշխատանքներում ապացուցել է, որ G գրաֆի տոտալ քրոմատիկ թիվը չի գերազանցում 6-ի (7-ի), երբ Delta(G) = 4 (Delta(G) = 5)։ Գրաֆների տոտալ քրոմատիկ թվի ընդհանուր գնահատականը տրվել է Մոլլոյի և Ռիդի [15] կողմից, որոնք ապացուցել են, որ X"(G) <= Delta(G) + 10^26 բոլոր գրաֆների համար։ Նշենք նաև, որ տոտալ քրոմատիկ թվի ճշգրիտ արժեքը հայտնի է միայն պարզ շղթաների, պարզ ցիկլերի, լրիվ և լրիվ երկկողմանի, n - չափանի խորանարդի [6, 31], լրիվ k - կողմանի գրաֆների համար, որոնց գագաթների քանակը կենտ է [9] և G հարթ գրաֆների համար, որոնց Delta(G) >= 9 [7, 8, 14, 25, 29, 32]։

Ներկա աշխատանքը շարունակում է հետազոտել գրաֆների տոտալ ներկումները, բայց մեկ լրացուցիչ պայմանով, որ ամեն մի գագաթի ընդլայնված շրջակայքը ներկված է հաջորդական գույներով։ Այս ներկումները սինթեզում են միջակայքային կողային ներկումները, որոնք ներմուծվել են [1, 2]-ում և գրաֆների տոտալ ներկումները։ Այս տիպի ներկումներին [16]-ում տրվել է միջակայքային տոտալ ներկման անվանումը։ [16, 17]-ում հեղինակի կողմից հետազոտվել են որոշ գրաֆների միջակայքային տոտալ ներկումների գոյության, կառուցման և պարամետրերի գնահատման հարցեր, իսկ որոշ դեպքերում գտնվել են այդպիսի ներկումներում մասնակցող գույների քանակի բոլոր հնարավոր արժեքները։ [18]-ում հեղինակների կողմից հետազոտվել են ծառերի միջակայքային տոտալ ներկումները, իսկ [20, 22]-ում ցույց է տրվել, որ համասեռ, ենթախորանարդ, (2,b)-երկհամասեռ, երկակի ուռուցիկ և որոշ Delta(G) <= 4 աստիճանն ունեցող երկկողմանի գրաֆներն ունեն միջակայքային տոտալ ներկում։ Նշենք նաև, որ ոչ բոլոր երկկողմանի գրաֆները ունեն միջակայքային տոտալ ներկում [20]։ Այդպիսի նվազագույն օրինակը կառուցվել է [26]-ում։

Այս աշխատանքում ուսումնասիրվել են կապակցված, համասեռ և կմախքային աստղ ունեցող գրաֆների միջակայքային տոտալ ներկումների գոյության, կառուցման և թվային պարամետրերի գնահատման հարցերը։ Նաև աշխատանքում ուսումնասիրվել են գրաֆների դեկարտյան արտադրյալների միջակայքային տոտալ ներկումները և տրվել են վերին գնահատականներ այդ ներկումներում մասնակցող գույների նվազագույն և առավելագույն հնարավոր թվերի համար։ Մասնավորապես, աշխատանքում ապացուցվել է, որ

• Կամայական n բնական թվի համար գոյություն ունի G գրաֆ այնպիսին, որ G є T և w(G)-X"(G) >= n,
• եթե G - ն կապակցված գրաֆ է և G - ն ունի միջակայքային տոտալ t - ներկում, ապա t <= 2|V(G)| - 1,
• եթե G - ն կապակցված r - համասեռ գրաֆ է, |V(G)| >= 2r + 2, և G - ն ունի միջակայքային տոտալ t - ներկում, ապա t <= 2|V(G)| - 3,
• հովհարները և անիվները ունեն միջակայքային տոտալ ներկումներ և գտնվել են այդպիսի ներկումներում մասնակցող գույների բոլոր հնարավոր արժեքները,
• Գրաֆների որոշ դեկարտյան արտադրյալների համար տրվել են վերին և ստորին գնահատականներ,
• Հարթ դեկարտյան արտադրյալների համար ապացուցվել է, որ եթե G*H արտադրյալի արտադրիչներից յուրաքանչյուրն ունի առնվազն 3 գագաթ, ապա G*H є T և w(G*H) = 5,
• Կառուցվել են մի շարք երկկողմանի գրաֆներ, որոնք չունեն միջակայքային տոտալ ներկում։

Ընդհանուր բնույթի արդյունքներ

Պնդում 3.1։ Եթե G - ն r - համասեռ գրաֆ է և X"(G) = r + 1, ապա G є T և

w(G) = X"(G)։

Պնդում 3.2։ Կամայական n բնական թվի համար գոյություն ունի G գրաֆ այնպիսին, որ G є T և

w(G) - X"(G) >= n։ 

Պնդում 3.3։ Կամայական n բնական թվի համար գոյություն ունի G գրաֆ այնպիսին, որ G є T և

W(G)-w(G) >= |V(G)| - 1։ 

Թեորեմ 3.1։ Եթե G - ն կապակցված գրաֆ է և G є T ապա

W(G) <= 2|V(G)| - 1։

Թեորեմ 3.2։ Եթե G - ն կապակցված r - համասեռ գրաֆ է այնպիսին, որ |V(G)| >= 2r + 2 և G є T, ապա

W(G) <= 2|V(G)| - 3։

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

1.
2. A.S. Asratian, R.R. Kamalian, Investigation on interval edge-colorings of graphs, Journal of Combin. Theory, Ser. B, vol. 62, 1994, pp. 34–43.
3. A.S. Asratian, T.M.J. Denley, R. Haggkvist, Bipartite graphs and their applications, Cambridge Tracts in Mathematics, 131, Cambridge University Press, 1998, 259 pp.
4. A.S. Asratian, C.J. Casselgren, On interval edge colorings of biregular bipartite graphs, Discrete Math. 307, 2006, pp. 1951–1956.
5. M. Behzad, Graphs and their chromatic numbers, Ph.D. thesis, Michigan State University, 1965.
6. M. Behzad, G. Chartrand, J.K. Cooper Jr., The colour numbers of complete graphs, J. London Math. Soc. 42, 1967, pp. 226–228.
7. O.V. Borodin, On the total colouring of planar graphs, J. Reine Angew. Math. 394, 1989, pp. 180–185.
8. O.V. Borodin, A.V. Kostochka, D.R. Woodall, Total colorings of planar graphs with large maximum degree, J. Graph Theory 26, 1997, pp. 53–59.
9. K.H. Chew, H.P. Yap, Total chromatic number of complete partite graphs, J. Graph Theory 16, 1992, pp. 629–634.
10. A.J.W. Hilton, H.R. Hind, Total chromatic number of graphs having large maximum degree, Discrete Math. 117, 1993, pp. 127–140.
11. T.R. Jensen, B. Toft, Graph Coloring Problems, Wiley Interscience Series in Discrete Mathematics and Optimization, 1995.
12. A.V. Kostochka, The total coloring of a multigraphs with maximal degree 4, Discrete Mathematics 17, 1977, pp. 161–163.
13. A.V. Kostochka, The total coloring of a multigraphs with maximal degree 5 is at most seven, Discrete Mathematics 162, 1996, pp. 199–214.
14. L. Kowalik, J.-S. Sereni, R. Skrekovski, Total-colouring of plane graphs with maximum degree nine, SIAM J. Discrete Math. 22, 2008, pp. 1462–1479.
15. M. Molloy, B. Reed, A bound on the total chromatic number, Combinatorica 18, 1998, pp. 241–280.
16. P.A. Petrosyan, Interval total colorings of complete bipartite graphs, Proceedings of the CSIT Conference, Yerevan, 2007, pp. 84–85.
17. P.A. Petrosyan, Interval total colorings of certain graphs, Mathematical Problems of Computer Science, Vol. 31, 2008, pp. 122–129.
18. P.A. Petrosyan, A.S. Shashikyan, On interval total colorings of trees, Mathematical Problems of Computer Science, Vol. 32, 2009, pp. 70–73.
19. P.A. Petrosyan, N.A. Khachatryan, Interval total colorings of graphs with a spanning star, Mathematical Problems of Computer Science, Vol. 32, 2009, pp. 78–85.
20. P.A. Petrosyan, A.S. Shashikyan, On interval total colorings of bipartite graphs, Proceedings of the CSIT Conference, 2009, pp. 95–98.
21. P.A. Petrosyan, A.Yu. Torosyan, Interval total colorings of complete graphs, Proceedings of the CSIT Conference, 2009, pp. 99–102.
22. P.A. Petrosyan, A.S. Shashikyan, On interval total colorings of doubly convex bipartite graphs, Mathematical Problems of Computer Science, Vol. 33, 2010, 54-58.
23. P.A. Petrosyan, N.A. Khachatryan, Upper bounds for the maximum span in interval total colorings of graphs, Mathematical Problems of Computer Science, Vol. 34, 2010, to appear.
24. M. Rosenfeld, On the total coloring of certain graphs, Israel J. Math. 9, 1971, pp. 396–402.
25. D.P. Sanders, Y. Zhao, On total 9-coloring planar graphs of maximum degree seven, J. Graph Theory 31, 1999, pp. 67–73.
26.
27. N. Vijayaditya, On the total chromatic number of a graph, J. London Math. Soc. (2) 3, 1971, pp. 405–408.
28.
29. W. Wang, Total chromatic number of planar graphs with maximum degree ten, J. Graph Theory 54, 2006, pp. 91–102.
30. D.B. West, Introduction to Graph Theory, Prentice-Hall, New Jersey, 1996.
31. H.P. Yap, Total colorings of graphs, Lecture Notes in Mathematics 1623, Springer-Verlag, Berlin, 1996.
32. Z. Zhang, J. Zhand, J. Wang, The total chromatic numbers of some graphs, Scientia Sinica A 31, 1988, pp. 1434–1441.
33. M. Behzad and E. S. Mahmoodian, On topological invariants of the product of graphs, Canad. Math. Bull. 12., 1969, 157-166.