×

zbMATH — the first resource for mathematics

Computing the boxicity of a graph by covering its complement by cointerval graphs. (English) Zbl 0524.05059

MSC:
05C99 Graph theory
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Cohen, J.E., Interval graphs and food webs: A finding and a problem, document 17696-PR, (30 August 1968), Rand Corporation Santa Monica, CA
[2] Cohen, J.E., Food webs and niche space, (1978), Princeton Univ. Press Princeton, NJ
[3] Cozzens, M.B., Higher and multi-dimensional analogues of interval graphs, ()
[4] Cozzens, M.B., The NP-completeness of the boxicity of a graph, (1982), submitted for publication
[5] Fishburn, P.C., Intransitive indifference with unequal indifference intervals, J. math. psychol., 7, 144-149, (1970) · Zbl 0191.31501
[6] Földes, S.; Hammer, P., Split graphs, (), 311-315
[7] Fulkerson, D.R.; Gross, O.A., Incidence matrices and interval graphs, Pacific J. math., 15, 835-855, (1965) · Zbl 0132.21001
[8] Gabai, H., Bounds for the boxicity of a graph, (1974), York College, City Univ. of New York, mimeo
[9] Gilmore, P.C.; Hoffman, A.J., A characterization of comparability graphs and of interval graphs, Canad. J. math., 16, 539-548, (1964) · Zbl 0121.26003
[10] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[11] Hammer, P.L.; Simeone, B., The splittance of a graph, () · Zbl 0492.05043
[12] P. Hanlon, Counting interval graphs, to appear. · Zbl 0519.05039
[13] Harary, F., Graph theory, (1969), Addison-Wesley Reading, MA · Zbl 0797.05064
[14] Kabell, J.A., Intersection graphs: structure and invariants, ()
[15] ()
[16] Lekkerkerker, C.B.; Boland, J.C., Representation of a finite graph by a set of intervals on the real line, Fund. math., 51, 45-64, (1962) · Zbl 0105.17501
[17] Opsut, R.J.; Roberts, F.S., On the fleet maintenance, mobile radio frequency, task assignment, and traffic phasing problems, (), 479-492 · Zbl 0471.05032
[18] Roberts, F.S., On the boxicity and cubicity of a graph, (), 301-310 · Zbl 0193.24301
[19] Roberts, F.S., Discrete mathematical models, with applications to social, biological, and environmental problems, (1976), Prentice-Hall Englewood Cliffs, NJ · Zbl 0363.90002
[20] Roberts, F.S., Food webs, competition graphs, and the boxicity of ecological phase space, (), 477-490
[21] Roberts, F.S., Graph theory and its applications to problems of society, () · Zbl 0193.24301
[22] Skrien, D., Interval graphs, chronological orderings, and related matters, () · Zbl 0543.05059
[23] Trotter, W.T., A forbidden subgraph characterization of Roberts’ inequality for boxicity, Discrete math., 28, 303-314, (1979)
[24] Wittenshausen, H.S., On intersections of interval graphs, Discrete math., 31, 211-216, (1980) · Zbl 0443.05061
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.