×

Complexity of dimension three and some related edge-covering characteristics of graphs. (English) Zbl 0442.68031


MSC:

68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
05C99 Graph theory

Keywords:

edge-covering
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA, Chapter 10. · Zbl 0207.01701
[2] Cook, S. A., The complexity of theorem proving procedures, Proc. 3rd Annual ACM Symposium on Theory of Computing, 151-158 (1971)
[3] Dushnik, B.; Miller, E. W., Partially ordered sets, Amer. J. Math., 63, 600-610 (1941) · Zbl 0025.31002
[4] Garey, M. R.; Johnson, D. S., The complexity of near optimal graph coloring, J. ACM, 23, 1, 43-49 (1976) · Zbl 0322.05111
[5] Garey, M. R.; Johnson, D. S.; Stockmeyer, L. J., Some simplified NP-complete problems, Theoret. Comput. Sci., 1, 237-267 (1976) · Zbl 0338.05120
[6] Johnson, D. S., Worst case behavior of graph colouring algorithms, (Proc. 5th South Eastern on Comb., Graph Th. and Comp. (1974), Utilities Math. Publ: Utilities Math. Publ Winnipeg), 513-528
[7] Karp, R. M., Reducibility among combinatorial problems, (Complexity of Computer Computations (1972), Plenum: Plenum New York), 85-104 · Zbl 1467.68065
[8] Karp, R. M., On the complexity of combinatorial problems, Networks, 5, 45-68 (1975) · Zbl 0324.05003
[10] Nešetřil, J.; Pultr, A., A Dushnik-Miller type dimension of graphs and its complexity, (Fundamentals of Computational Theories. Fundamentals of Computational Theories, Lecture Notes in Computer Science, 56 (1977), Springer: Springer Berlin), 482-493 · Zbl 0362.05073
[11] Nešetřil, J.; Rödl, V., A simple proof of the Galvin-Ramsey property of the class of all finite graphs and a dimension of a graph, Discrete Math., 23, 49-55 (1978) · Zbl 0388.05036
[12] Ore, O., Theory of graphs, (AMS, Vol. XXXVIII (1962), AMS: AMS Providence, RI)
[13] Stockmeyer, L. J., Planar 3-colorability is polynomial complete, Sigact News, 5, 3, 19-25 (1973)
[14] Vizing, V. G., On an estimate of the chromatic class of a \(p\)-graph, Diskret. Analiz, 3, 25-30 (1964), (in Russian)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.