×

Interval bigraphs and circular arc graphs. (English) Zbl 1046.05066

Summary: We prove that the complements of interval bigraphs are precisely those circular arc graphs of clique covering number two, which admit a representation without two arcs covering the whole circle. We give another characterization of interval bigraphs, in terms of a vertex ordering, that we hope may prove helpful in finding a more efficient recognition algorithm than presently known. We use these results to show equality, amongst bipartite graphs, of several classes of structured graphs (proper interval bigraphs, complements of proper circular arc graphs, asteroidal-triple-free graphs, permutation graphs, and co-comparability graphs). Our results verify a conjecture of Lundgren and disprove a conjecture of H. Müller [Discrete Appl. Math. 78, 189–205 (1997; Zbl 0890.68103)].

MSC:

05C75 Structural characterization of families of graphs

Citations:

Zbl 0890.68103
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Booth, J Comput Syst Sci 13 pp 335– (1976) · Zbl 0367.68034
[2] and Graph Classes, SIAM Monographs Discrete Math and Applications, Philadelphia, 1999.
[3] Brown, Congressus Num 149 pp 77– (2001)
[4] Brown, Congressus Num 157 pp 79– (2002)
[5] and Several characterizations of unit interval bigraphs, manuscript 2003.
[6] A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs, manuscript 2002.
[7] Corneil, Inform Process Lett 55 pp 99– (1995)
[8] and A multipass LBFS algorithm for the recognition of interval graphs, manuscript 2000.
[9] Deng, SIAM J Comput 25 pp 390– (1996)
[10] Feder, J Combin Theory B 72 pp 236– (1998)
[11] Feder, Combinatorica 19 pp 487– (1999)
[12] Feder, J Graph Theory 42 pp 61– (2003)
[13] Gallai, Acta Math Acad Sci Hungar 18 pp 25– (1967)
[14] and Tolerance Graphs, Cambridge University Press, 2004.
[15] Harary, Math Universitatis Carolinae 23 pp 739– (1982)
[16] Hell, Graphs and Combinatorics 13 pp 65– (1997)
[17] and Certifying LexBFS recognition algorithms for proper interval graphs, and proper interval bigraphs, manuscript 2003.
[18] Hsu, J Algorithms 43 pp 1– (2002)
[19] Lekkerkerker, Fund Math 51 pp 45– (1962)
[20] Lin, Congressus Num 125 pp 201– (1997)
[21] Variations on interval graphs, presentation at the SIAM Conference on Discrete Mathematics, San Diego, August 2002.
[22] Linear-time recognition of circular arc graphs, Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS01) 42, 2001.
[23] Müller, Discrete Appl Math 78 pp 189– (1997)
[24] A journey through intersection graph county, web manuscript, http://www.math.uni-hamburg.de/spag/gd/mitarbeiter/prisner/Pris/Rahmen.html.
[25] Sanyal, J Graph Theory 22 pp 297– (1996)
[26] and Bigraphs of Ferrers dimension two and circular arc graphs, manuscript 2003.
[27] Sen, J Graph Theory 13 pp 189– (1989)
[28] Spinrad, J Combin Theory B pp 300– (1988)
[29] web manuscript of a book, http://www.vuse.vanderbilt.edu/spin/book.ps (see section 13.4.2).
[30] Spinrad, Discrete Appl Math 18 pp 279– (1987)
[31] Trotter, Discrete Math 16 pp 361– (1976)
[32] Tucker, Discrete Math 7 pp 167– (1974)
[33] Tucker, Pacific J Math 39 pp 535– (1971) · Zbl 0226.05125
[34] Tucker, SIAM J Comput 9 pp 1– (1980)
[35] Eigenschaften der nerven homologische-einfactor familien in Rn, Ph.D. thesis, Universität Gottigen, Gottingen, Germany, 1967.
[36] West, Discrete Math 178 pp 287– (1998)
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.