References

• Aho, A. V., Garey, M. R., & Ullman, J. D. (1972). The Transitive Reduction of a Directed Graph. SIAM Journal on Computing, 1(2), 131–137. https://doi.org/10.1137/0201008
• Berman, P., Karpinski, M., & Scott, A. D. (2007). Computational complexity of some restricted instances of 3-SAT. Discrete Applied Mathematics, 155(5), 649–653. https://doi.org/10.1016/j.dam.2006.07.009
• Brooks, R. L. (1941). On colouring the nodes of a network. Mathematical Proceedings of the Cambridge Philosophical Society, 37(2), 194–197. https://doi.org/10.1017/s030500410002168x
• Burr, S. A., Erdős, P., & Lovasz, L. (1976). On graphs of Ramsey type. ARS COMBINATORIA, 1.
• Cockayne, E., Goodman, S., & Hedetniemi, S. (1975). A linear algorithm for the domination number of a tree. Information Processing Letters, 4(2), 41–44. https://doi.org/10.1016/0020-0190(75)90011-3
• Cockayne, E., & Hedetniemi, S. (1975). Optimal domination in graphs. IEEE Transactions on Circuits and Systems, 22(11), 855–857. https://doi.org/10.1109/tcs.1975.1083994
• Cook, S. A. (1971). The complexity of theorem-proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing - STOC ’71. https://doi.org/10.1145/800157.805047
• Dantzig, G. B. (1957). Discrete-Variable Extremum Problems. Operations Research, 5(2), 266–288. https://doi.org/10.1287/opre.5.2.266
• Ehrlich, G., Even, S., & Tarjan, R. E. (1976). Intersection graphs of curves in the plane. Journal of Combinatorial Theory, Series B, 21(1), 8–20. https://doi.org/10.1016/0095-8956(76)90022-8
• Even, S., Pnueli, A., & Lempel, A. (1972). Permutation Graphs and Transitive Graphs. Journal of the ACM, 19(3), 400–410. https://doi.org/10.1145/321707.321710
• Even, S., Itai, A., & Shamir, A. (1976). On the Complexity of Timetable and Multicommodity Flow Problems. SIAM Journal on Computing, 5(4), 691–703. https://doi.org/10.1137/0205048
• Garey, M. R., Johnson, D. S., & Tarjan, R. E. (1976). The Planar Hamiltonian Circuit Problem is NP-Complete. SIAM Journal on Computing, 5(4), 704–714. https://doi.org/10.1137/0205049
• Garey, M. R., Johnson, D. S., & Stockmeyer, L. (1976). Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3), 237–267. https://doi.org/10.1016/0304-3975(76)90059-1
• Garey, M. R., & Johnson, D. S. (1977). The Rectilinear Steiner Tree Problem is $NP$-Complete. SIAM Journal on Applied Mathematics, 32(4), 826–834. https://doi.org/10.1137/0132071
• Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co.
• Garfinkel, R. S. (1977). Minimizing Wallpaper Waste, Part 1: A Class of Traveling Salesman Problems. Operations Research, 25(5), 741–751. https://doi.org/10.1287/opre.25.5.741
• Gavril, F. (1972). Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph. SIAM Journal on Computing, 1(2), 180–187. https://doi.org/10.1137/0201013
• Gavril, F. (1973). Algorithms for a maximum clique and a maximum independent set of a circle graph. Networks, 3(3), 261–273. https://doi.org/10.1002/net.3230030305
• Gavril, F. (1974). Algorithms on circular-arc graphs. Networks, 4(4), 357–369. https://doi.org/10.1002/net.3230040407
• Gavril, F. (1977). “Some NP-complete problems on graphs”, Proc. 11th Conf. on Information Sciences and Systems, Johns Hopkins University, Baltimore, MD.
• Gilmore, P. C., & Gomory, R. E. (1964). Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem. Operations Research, 12(5), 655–679. https://doi.org/10.1287/opre.12.5.655
• Gold, E. M. (1978). Complexity of automaton identification from given data. Information and Control, 37(3), 302–320. https://doi.org/10.1016/s0019-9958(78)90562-4
• Golumbic, M. C. (1977). The complexity of comparability graph recognition and coloring. Computing, 18(3), 199–208. https://doi.org/10.1007/bf02253207
• Hadlock, F. (1975). Finding a Maximum Cut of a Planar Graph in Polynomial Time. SIAM Journal on Computing, 4(3), 221–225. https://doi.org/10.1137/0204019
• Harary, F. (1969). Graph theory. Addison-Wesley Publishing Company.
• Karaganis, J. J. (1968). On the Cube of a Graph. Canadian Mathematical Bulletin, 11(2), 295–296. https://doi.org/10.4153/cmb-1968-037-0
• Karp, R. M. (1972). Reducibility among Combinatorial Problems. In Complexity of Computer Computations (pp. 85–103). Springer US. https://doi.org/10.1007/978-1-4684-2001-2_9
• Kirkpatrick, D. G., & Hell, P. (1978). On the completeness of a generalized matching problem. Proceedings of the Tenth Annual ACM Symposium on Theory of Computing - STOC ’78. https://doi.org/10.1145/800133.804353
• Kou, L. T., Stockmeyer, L. J., & Wong, C. K. (1978). Covering edges by cliques with regard to keyword conflicts and intersection graphs. Communications of the ACM, 21(2), 135–139. https://doi.org/10.1145/359340.359346
• Krishnamoorthy, M. S. (1975). An NP-hard problem in bipartite graphs. ACM SIGACT News, 7(1), 26–26. https://doi.org/10.1145/990518.990521
• Lawler, E. L. (1976). Combinatorial optimization: networks and matroids. Holt, Rinehart.
• Lichtenstein, D. (1982). Planar Formulae and Their Uses. SIAM Journal on Computing, 11(2), 329–343. https://doi.org/10.1137/0211025
• Liu, C. L. (1968). Introduction to combinatorial mathematics. McGraw-Hill.
• Lucchesi, C. L. (1976). A Minimax Equality for Directed Graphs. Thesis (Ph.D.)–University of Waterloo.
• Maheshwari, S. (1976). Traversal Marker Placement Problems Are NP-Complete ; CU-CS-092-76.
• Maier, D., & Storer, J. (1977). A note on the complexity of the superstring problem Technical Report 233. Princeton University, Department of Electrical Engineering and Computer Science, Princeton, NJ.
• Minty, G. J. (1980). On maximal independent sets of vertices in claw-free graphs. Journal of Combinatorial Theory, Series B, 28(3), 284–304. https://doi.org/10.1016/0095-8956(80)90074-x
• Mitchell, S. (1977). Edge domination in trees. Proc. 8th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, 1977. https://ci.nii.ac.jp/naid/10022184453/en/
• Morrow, C., & Goodman, S. (1976). An efficient algorithm for finding a longest cycle in a tournament. Proc. 7th Southeastern Conference on Combinatorics, Graph Theory, and Computing, 453–462.
• Orlin, J. (1977). Contentment in graph theory: Covering graphs with cliques. Indagationes Mathematicae (Proceedings), 80(5), 406–424. https://doi.org/10.1016/1385-7258(77)90055-5
• Orlova, G., & Dorfman, Y. (1972). Finding the Maximum Cut in a Graph. Engineering Cybernetics, 10, 502–506. https://ci.nii.ac.jp/naid/10022525097/en/
• Papadimitriou, C. H., & Steiglitz, K. (1976). Some complexity results for the Traveling Salesman Problem. Proceedings of the Eighth Annual ACM Symposium on Theory of Computing - STOC ’76. https://doi.org/10.1145/800113.803625
• Plesnik, J. (1979). The np-completeness of the hamiltonian cycle problem in planar diagraphs with degree bound two. Information Processing Letters, 8(4), 199–201. https://doi.org/10.1016/0020-0190(79)90023-1
• Poljak, S. (1974). A note on stable sets and colorings of graphs. Commentationes Mathematicae Universitatis Carolinae, 15(2), 307–309. http://eudml.org/doc/16622
• Sahni, S. (1974). Computationally Related Problems. SIAM Journal on Computing, 3(4), 262–279. https://doi.org/10.1137/0203021
• Sahni, S., & Gonzalez, T. (1976). P-Complete Approximation Problems. Journal of the ACM, 23(3), 555–565. https://doi.org/10.1145/321958.321975
• Schaefer, T. J. (1978). The complexity of satisfiability problems. Proceedings of the Tenth Annual ACM Symposium on Theory of Computing - STOC ’78. https://doi.org/10.1145/800133.804350
• Shamir, A. (1977). Finding Minimum Cutsets in Reducible Graphs [Techreport]. MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE.
• Sysło, M. M. (1973). A new solvable case of the traveling salesman problem. Mathematical Programming, 4(1), 347–348. https://doi.org/10.1007/bf01584676
• Walsh, A. M., & Burkhard, W. A. (1977). Efficient algorithms for (3, 1) graphs. Information Sciences, 13(1), 1–10. https://doi.org/10.1016/0020-0255(77)90009-3
• Yannakakis, M. (1978). Node-and edge-deletion NP-complete problems. Proceedings of the Tenth Annual ACM Symposium on Theory of Computing - STOC ’78. https://doi.org/10.1145/800133.804355
• Yannakakis, M., & Gavril, F. (1980). Edge Dominating Sets in Graphs. SIAM Journal on Applied Mathematics, 38(3), 364–372. https://doi.org/10.1137/0138030