Split graphs of Dilworth number 2. (English) Zbl 0573.05047
In this paper is given a short outline of results concerning to graphs with Dilworth number at most 2. There is proved the equivalence of split graphs with Dilworth number at most 2 and the class of graphs G such that G and its complement \(\bar G\) are interval graphs. There is also given a characterisation of such graphs by means of forbidden graphs.
Reviewer: L.Niepel
MSC:
| 05C99 | Graph theory |
References:
| [1] | Akiyama, J.; Ando, K.; Harary, F., A graph and its complement with specified properties VIII: interval graphs, Mimeograph (1983) |
| [2] | C. Benzaken, P.L. Hammer and D. de Werra, Threshold characterization of graphs with Dilworth number two, J. Graph Theory, to appear.; C. Benzaken, P.L. Hammer and D. de Werra, Threshold characterization of graphs with Dilworth number two, J. Graph Theory, to appear. · Zbl 0583.05048 |
| [3] | Chvátal, V.; Hammer, P. L., Aggregation of inequalities in integer programming, Ann. Discrete Math., 1, 145-162 (1977) · Zbl 0384.90091 |
| [4] | Foldes, S.; Hammer, P. L., Split graphs, Congress. Numer., 311-315 (1978) · Zbl 0395.05021 |
| [5] | Foldes, S.; Hammer, P. L., Split graphs having Dilworth number 2, Canad. J. Math., 29, 666-672 (1977) · Zbl 0335.05130 |
| [6] | Gilmore, P. C.; Hoffman, A., A characterization of comparability graphs and of interval graphs, Canad. J. Math., 16, 539-548 (1964) · Zbl 0121.26003 |
| [7] | Golumbic, M., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054 |
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.
