«Գրաֆների միջակայքային տոտալ ներկումներ»–ի խմբագրումների տարբերություն

Content deleted Content added
No edit summary
չ clean up oգտվելով ԱՎԲ (9411)
Տող 2.
 
==Ներածություն==
 
 
Ներկումների խնդիրները հանդիսանում են դիսկրետ մաթեմատիկայի հայտնի և արդի հետազոտման թեմաներից մեկը: Այդ խնդիրների կարևորությունը պայմանավորված է առկա սերտ կապով մի շարք կարևոր կիրառական խնդիրների հետ: Մասնավորապես, նշանակելի փոխադարձ կապ կա կարգացուցակների տեսության խնդիրների և գրաֆների ներկումների խնդիրների միջև: Օրինակ, քննաշրջանի օպտիմալ կարգացուցակ կառուցելու խնդիրը բերվում է գրաֆի քրոմատիկ թվի որոշմանը: Գրաֆի քրոմատիկ դասը գտնելու խնդրին բերվում է սպորտային մրցումների կարգացուցակ կազմելու խնդիրը, իսկ երկկողմանի գրաֆների հատուկ տիպի կողային ներկումների խնդիրները բազմաթիվ աշխատանքներում ծառայել են որպես ուսումնական դասացուցակների գոյության, կառուցման թվային պարամետրերի գնահատման հարցերի հետազոտման մոդելներ:
 
 
Գրաֆների տոտալ ներկումները ներմուծվել են Վ. Վիզինգի և Մ. Բեհզադի [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]-ում:
 
 
Այս աշխատանքում ուսումնասիրվել են կապակցված, համասեռ և կմախքային աստղ ունեցող գրաֆների միջակայքային տոտալ ներկումների գոյության, կառուցման և թվային պարամետրերի գնահատման հարցերը: Նաև աշխատանքում ուսումնասիրվել են գրաֆների դեկարտյան արտադրյալների միջակայքային տոտալ ներկումները և տրվել են վերին գնահատականներ այդ ներկումներում մասնակցող գույների նվազագույն և առավելագույն հնարավոր թվերի համար: Մասնավորապես, աշխատանքում ապացուցվել է, որ
Տող 21 ⟶ 17՝
* Գրաֆների որոշ դեկարտյան արտադրյալների համար տրվել են վերին և ստորին գնահատականներ,
* Հարթ դեկարտյան արտադրյալների համար ապացուցվել է, որ եթե G*H արտադրյալի արտադրիչներից յուրաքանչյուրն ունի առնվազն 3 գագաթ, ապա G*H є T և w(G*H) = 5,
* Կառուցվել են մի շարք երկկողմանի գրաֆներ, որոնք չունեն միջակայքային տոտալ ներկում:
 
 
==Ընդհանուր բնույթի արդյունքներ==
Տող 36 ⟶ 31՝
Թեորեմ 3.2: Եթե G - ն կապակցված r - համասեռ գրաֆ է այնպիսին, որ |V(G)| >= 2r + 2 և G є T, ապա
W(G) <= 2|V(G)| - 3:
 
==Գրականություն==
 
 
1.<br />
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&nbsp;34–43.<br />
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.<br />
4. A.S. Asratian, C.J. Casselgren, On interval edge colorings of biregular bipartite graphs, Discrete Math. 307, 2006, pp. 1951-1956&nbsp;1951–1956.<br />
5. M. Behzad, Graphs and their chromatic numbers, Ph.D. thesis, Michigan State University, 1965.<br />
6. M. Behzad, G. Chartrand, J.K. Cooper Jr., The colour numbers of complete graphs, J. London Math. Soc. 42, 1967, pp. 226-228&nbsp;226–228.<br />
7. O.V. Borodin, On the total colouring of planar graphs, J. Reine Angew. Math. 394, 1989, pp. 180-185&nbsp;180–185.<br />
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&nbsp;53–59.<br />
9. K.H. Chew, H.P. Yap, Total chromatic number of complete partite graphs, J. Graph Theory 16, 1992, pp. 629-634&nbsp;629–634.<br />
10. A.J.W. Hilton, H.R. Hind, Total chromatic number of graphs having large maximum degree, Discrete Math. 117, 1993, pp. 127-140&nbsp;127–140.<br />
11. T.R. Jensen, B. Toft, Graph Coloring Problems, Wiley Interscience Series in Discrete Mathematics and Optimization, 1995.<br />
12. A.V. Kostochka, The total coloring of a multigraphs with maximal degree 4, Discrete Mathematics 17, 1977, pp. 161-163&nbsp;161–163.<br />
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&nbsp;199–214.<br />
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&nbsp;1462–1479.<br />
15. M. Molloy, B. Reed, A bound on the total chromatic number, Combinatorica 18, 1998, pp. 241-280&nbsp;241–280.<br />
16. P.A. Petrosyan, Interval total colorings of complete bipartite graphs, Proceedings of the CSIT Conference, Yerevan, 2007, pp. 84-85&nbsp;84–85.<br />
17. P.A. Petrosyan, Interval total colorings of certain graphs, Mathematical Problems of Computer Science, Vol. 31, 2008, pp. 122-129&nbsp;122–129.<br />
18. P.A. Petrosyan, A.S. Shashikyan, On interval total colorings of trees, Mathematical Problems of Computer Science, Vol. 32, 2009, pp. 70-73&nbsp;70–73.<br />
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&nbsp;78–85.<br />
20. P.A. Petrosyan, A.S. Shashikyan, On interval total colorings of bipartite graphs, Proceedings of the CSIT Conference, 2009, pp. 95-98&nbsp;95–98.<br />
21. P.A. Petrosyan, A.Yu. Torosyan, Interval total colorings of complete graphs, Proceedings of the CSIT Conference, 2009, pp. 99-102&nbsp;99–102.<br />
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.<br />
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.<br />
24. M. Rosenfeld, On the total coloring of certain graphs, Israel J. Math. 9, 1971, pp. 396-402&nbsp;396–402.<br />
25. D.P. Sanders, Y. Zhao, On total 9-coloring planar graphs of maximum degree seven, J. Graph Theory 31, 1999, pp. 67-73&nbsp;67–73.<br />
26.<br />
27. N. Vijayaditya, On the total chromatic number of a graph, J. London Math. Soc. (2) 3, 1971, pp. 405-408&nbsp;405–408.<br />
28.<br />
29. W. Wang, Total chromatic number of planar graphs with maximum degree ten, J. Graph Theory 54, 2006, pp. 91-102&nbsp;91–102.<br />
30. D.B. West, Introduction to Graph Theory, Prentice-Hall, New Jersey, 1996.<br />
31. H.P. Yap, Total colorings of graphs, Lecture Notes in Mathematics 1623, Springer-Verlag, Berlin, 1996.<br />
32. Z. Zhang, J. Zhand, J. Wang, The total chromatic numbers of some graphs, Scientia Sinica A 31, 1988, pp. 1434-1441&nbsp;1434–1441.<br />
33. M. Behzad and E. S. Mahmoodian, On topological invariants of the product of graphs, Canad. Math. Bull. 12., 1969, 157-166.