Interval Edge Colourings of Complete Graphs and n-cubes
Abstract
For complete graphs and n-cubes bounds are found for the possible number of colours in an interval edge colourings.
References
F.Harary, "Graph Theory",Addison-Wesley,Reading, MA,1969.
A.A.Zykov,"Theory of fiite graphs",Novosibirsk,Nauka, 1969.
A S.Asratian,R.R.Kamalian,"Interval colourings of edges of a multigraph",Appl. Math.5,Yerevan State University,pp.25-34 1987.
R.R.Kamalian,"Interval Edge Colourings of Graphs",Doctoral dissertation,The Institute of Mathematics of the Siberian Branch of the Academy of Sciences of USSR,Novosibirsk,1990.
S.V.Sevastianov, " On interval colourability of edges of abipartite graph",Meth. Of Discr.Anal. In solution of extremal problems. The Institute of Mathematics of the Siberian Branch of the Academy of S ciences of USSR,Novosibirsk, N50,pp.61-72,1990.
S. Cook,"The complexity of theorem-proving procedures."In Proc.3rd ACM Symp.on Theory of Computing, pp.151 -158,1971.
R.M.Karp," Reducibility among Combinatorial Problems",in Complexity of Computer Computations (R.E.Miller and J.W.Thatcher,Eds.),pp. 85-103, New York,Plenum,1972.
A.S.A sratian,R.R.Kamalian,"Investigation on interval edge colourings of graphs",J.Combin.Theory Ser.B62 pp.34-43,1994.
K.Giaro,M.Kubale,M.Malaejski,"Consecutive colourings of the edges of general graphs",Discr.Math. 236,pp.131 -143,2001.
I.Holyer,"The NP-completeness of edge colouring",SIAM J.Comput.10,N4,pp.71 8-720,1981.
V.G.Vizing,"The chromatic index of a multigraph",Kibernetika 3,pp.29-39 1965.
R.R. Kamalian,P.A.Petrosyan,"On lower bound for W(K2n) " , Mathematical Problems of Computer Science,Vol.23, pp.127-129,Yerevan,2004.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
