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

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

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

Գրաֆների տոտալ ներկումները ներմուծվել են Վ. Վիզինգի և Մ. Բեհզադի [5] կողմից 60-ական թվականներին։ G գրաֆի տոտալ ներկումը դա այդ գրաֆի գագաթների և կողերի ներկում է, որի դեպքում հարևան գագաթները, կողերը և կից գագաթները և կողերը ներկվում են տարբեր գույներով։ G գրաֆի X"(G) տոտալ քրոմատիկ թվի տակ հասկանում են այն նվազագույն գույների քանակը, որն անհրաժեշտ է G գրաֆի տոտալ ներկման համար։ Նշենք նաև, որ [5,28]-ում առաջարկվել է հիպոթեզ, համաձայն որի X"(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) = 9 [7, 8, 14, 25, 29, 32]։

Ներկա աշխատանքը շարունակում է հետազոտել գրաֆների տոտալ ներկումները, բայց մեկ լրացուցիչ պայմանով, որ ամեն մի գագաթի ընդլայնված շրջակայքը ներկված է հաջորդական գույներով։ Այս ներկումները սինթեզում են միջակայքային կողային ներկումները, որոնք ներմուծվել են [1, 2]-ում և գրաֆների տոտալ ներկումները։ Այս տիպի ներկումներին [16]-ում տրվել է միջակայքային տոտալ ներկման անվանումը։ [16, 17]-ում հեղինակի կողմից հետազոտվել են որոշ գրաֆների միջակայքային տոտալ ներկումների գոյության, կառուցման և պարամետրերի գնահատման հարցեր, իսկ որոշ դեպքերում գտնվել են այդպիսի ներկումներում մասնակցող գույների քանակի բոլոր հնարավոր արժեքները։ [18]-ում հեղինակների կողմից հետազոտվել են ծառերի միջակայքային տոտալ ներկումները, իսկ [20, 22]-ում ցույց է տրվել, որ համասեռ, ենթախորանարդ, (2,b)-երկհամասեռ, երկակի ուռուցիկ և որոշ Delta(G) = n, 
*	եթե G - ն կապակցված գրաֆ է և G - ն ունի միջակայքային տոտալ t - ներկում, ապա t = 2r + 2, և G - ն ունի միջակայքային տոտալ t - ներկում, ապա t = n։ 
Պնդում 3.3։ Կամայական n բնական թվի համար գոյություն ունի G գրաֆ այնպիսին, որ G є T և
 W(G)-w(G) >= |V(G)| - 1։ 
Թեորեմ 3.1։ Եթե G - ն կապակցված գրաֆ է և G є T ապա
 W(G) = 2r + 2 և G є T, ապա
 W(G) 
2.	A.S. Asratian, R.R. Kamalian, Investigation on interval edge-colorings of graphs, Journal of Combin. Theory, Ser. B, vol. 62, 1994, pp.&nbsp;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.&nbsp;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.&nbsp;226–228.
7.	O.V. Borodin, On the total colouring of planar graphs, J. Reine Angew. Math. 394, 1989, pp.&nbsp;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.&nbsp;53–59.
9.	K.H. Chew, H.P. Yap, Total chromatic number of complete partite graphs, J. Graph Theory 16, 1992, pp.&nbsp;629–634.
10.	 A.J.W. Hilton, H.R. Hind, Total chromatic number of graphs having large maximum degree, Discrete Math. 117, 1993, pp.&nbsp;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.&nbsp;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.&nbsp;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.&nbsp;1462–1479.
15.	M. Molloy, B. Reed, A bound on the total chromatic number, Combinatorica 18, 1998, pp.&nbsp;241–280.
16.	P.A. Petrosyan, Interval total colorings of complete bipartite graphs, Proceedings of the CSIT Conference, Yerevan, 2007, pp.&nbsp;84–85.
17.	P.A. Petrosyan, Interval total colorings of certain graphs, Mathematical Problems of Computer Science, Vol. 31, 2008, pp.&nbsp;122–129.
18.	P.A. Petrosyan, A.S. Shashikyan, On interval total colorings of trees, Mathematical Problems of Computer Science, Vol. 32, 2009, pp.&nbsp;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.&nbsp;78–85.
20.	P.A. Petrosyan, A.S. Shashikyan, On interval total colorings of bipartite graphs, Proceedings of the CSIT Conference, 2009, pp.&nbsp;95–98.
21.	P.A. Petrosyan, A.Yu. Torosyan, Interval total colorings of complete graphs, Proceedings of the CSIT Conference, 2009, pp.&nbsp;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.&nbsp;396–402.
25.	D.P. Sanders, Y. Zhao, On total 9-coloring planar graphs of maximum degree seven, J. Graph Theory 31, 1999, pp.&nbsp;67–73.
26.
27.	N. Vijayaditya, On the total chromatic number of a graph, J. London Math. Soc. (2) 3, 1971, pp.&nbsp;405–408.
28.
29.	W. Wang, Total chromatic number of planar graphs with maximum degree ten, J. Graph Theory 54, 2006, pp.&nbsp;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.&nbsp;1434–1441.
33.	M. Behzad and E. S. Mahmoodian, On topological invariants of the product of graphs, Canad. Math. Bull. 12., 1969, 157-166.

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