×

Acyclic orientations of a graph and the chromatic and independence numbers. (English) Zbl 0331.05110


MSC:

05C20 Directed graphs (digraphs), tournaments
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berge, C., (Graphs and Hypergraphs (1973), North-Holland and Elsevier: North-Holland and Elsevier Amsterdam) · Zbl 0483.05029
[2] Edmonds, J., Paths, trees, and flowers, Canad. J. Math., 17, 449-467 (1965) · Zbl 0132.20903
[3] Ford, L. R.; Fulkerson, D. R., (Flows in Networks (1962), Princeton Univ. Press: Princeton Univ. Press Princeton, N. J) · Zbl 0106.34802
[4] Gale, D., (The Theory of Linear Economic Models (1960), McGraw-Hill: McGraw-Hill New York) · Zbl 0114.12203
[5] Gallai, T., On directed paths and circuits, (Erdos, P.; Katona, G., Theory of Graphs (1968), Academic Press), 115-118, Tihany · Zbl 0159.54403
[6] Garfinkel, R.; Nemhauser, G., A survey of integer programming, (Hu, T. C.; Robinson, S. M., Mathematical Programming (1973), Academic Press: Academic Press New York) · Zbl 0271.90028
[7] Gilmore, P.; Hoffman, A. J., A characterization of comparability graphs and interval graphs, Canad. J. Math., 16, 539-548 (1964) · Zbl 0121.26003
[8] Harary, F., (Graph Theory (1969), Addison-Wesley Reading: Addison-Wesley Reading Mass) · Zbl 0182.57702
[9] Harary, F.; Norman, R. S.; Cartwright, D., (Structural Models (1965), Wiley: Wiley New York)
[10] Karp, R. M., (Reducibility Among Combinatorial Problems (1972), Computer Science, University of California: Computer Science, University of California Berkeley), Tech. Report 3 · Zbl 1467.68065
[11] Koenig, D., (Theorie der Endlichen und Unendlichen Graphen (1936), Leipzig) · JFM 62.0654.05
[12] Liu, C. L., (Topics in Combinatorial Mathematics (1972), Math. Assoc. Amer)
[13] Minty, G. J., A theorem on \(n\)-coloring the points of a linear graph, Amer. Math. Monthly, 69, 623-624 (1962) · Zbl 0108.36601
[14] Ore, O., (Theory of Graphs (1962)), Amer. Math. Soc. Colloq. Publ. 38, Providence, R.I.
[15] Pneuli, A.; Lempel, A.; Even, S., Transitive orientations of graphs and identification of permutation graphs, Canad. J. Math., 23, 160-175 (1971) · Zbl 0204.24604
[16] Roy, B., Nombre Chromatique et Plus Longs Chemins d’un Graphs, Revue AFIRO, 1, 127-132 (1967) · Zbl 0157.31302
[17] Ryser, H. J., Combinatorial Mathematics (1963), Math. Assoc. of Amer. Carus Monographs No. 14
[18] Trotter, L. E., (Solution Characteristics and Algorithms for the Vertex-Packing Problem (1973), Cornell U: Cornell U Ithaca, New York), Tech. Report 168 Op. Res.
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.