On Lower Bound for W(K2n)
Abstract
The lower bound W(K2n) ≥ 3n – 2 is proved for the greatest possible number of colors in an interval edge coloring of the complete graph K2n.
References
F. Harary, Graph Theory, Addison-Wesley, Reading, MA ,1969.
A.S. Asratian, R.R. Kamalian, Interval colorings of edges of a multigraph, Appl. Math.5, 25-34,1987.
S.V. Sevastianov, On interval colourability of edges of a bipartite graph, Meth. Of Discr. Anal. In solution of external problems. The Institute of Mathematics of the Siberian Branch of the Academy of Sciences of U SSR. Novosibirsk, N 50, 61-72, 1990.
S. Cook, The complexity of theorem-proving procedures. In P roc.3rd ACM Symp. on Theory of Computing, 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.
R.R. Kamalian, Interval Edge Colorings of Graphs, Doctoral dissertation, Novosibirsk, 1990.
K. Giaro, M. Kubale, M. Malafiejski, Consecutive colorings of the edges of general graphs, Discr. Math. 236, 131-143,2001.
A.A. Zykov, Theory of finite graphs, Novosibirsk, Nauka, 1969.
A.S. Asratian, R.R. Kamalian, Investigation on interval edge colorings of graphs, J. Combin. Theory Ser. B 62, 34-43,1994.
V.G. Vizing, The chromatic index of a multigraph, Kibernetika 3, 29-39, 1965.
I. Holyer, The NP-completeness of edge coloring, SIAM J. Comput. 10, N 4, 718-720, 1981.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
