Mixed unit interval bigraphs. (English) Zbl 1400.05200
Panda, B. S. (ed.) et al., Algorithms and discrete applied mathematics. 4th international conference, CALDAM 2018, Guwahati, India, February 15–17, 2018. Proceedings. Cham: Springer (ISBN 978-3-319-74179-6/pbk; 978-3-319-74180-2/ebook). Lecture Notes in Computer Science 10743, 15-29 (2018).
Summary: The class of intersection bigraphs of unit intervals of the real line whose ends may be open or closed is called mixed unit interval bigraphs. This class of bigraphs is a strict superclass of the class of unit interval bigraphs. We provide several infinite families of forbidden induced subgraphs of mixed unit interval bigraphs. We also pose a conjecture concerning characterization of mixed unit interval bigraphs and verify parts of it.
For the entire collection see [Zbl 1382.68013].
For the entire collection see [Zbl 1382.68013].
MSC:
| 05C75 | Structural characterization of families of graphs |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
References:
| [1] | Bogart, KP; West, DB, A short proof that “proper=unit”, Discret. Math., 201, 21-23, 1999 · Zbl 0932.05065 · doi:10.1016/S0012-365X(98)00310-0 |
| [2] | Corneil, DG, A simple 3-sweep LBFS algorithm for recognition of unit interval graphs, Discret. Appl. Math., 138, 371-379, 2004 · Zbl 1042.05067 · doi:10.1016/j.dam.2003.07.001 |
| [3] | Corneil, D.G., Olariu, S., Stewart, L.: The ultimate interval graph recognition algorithm? (Extended abstract). In: Proceedings of the 9th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pp. 175-180 (1998) · Zbl 0930.68105 |
| [4] | Das, A.K., Sahu, R.: A characterization of unit interval bigraphs of open and closed intervals. J. Graph Theory (under revision) · Zbl 1531.05216 |
| [5] | Das, AK; Das, S.; Sen, M., Forbidden substructure for interval digraphs/bigraphs, Discret. Math., 339, 1028-1051, 2016 · Zbl 1327.05132 · doi:10.1016/j.disc.2015.10.010 |
| [6] | Dourado, MC; Le, VB; Protti, F.; Rautenbach, D.; Szwarcfiter, JL, Mixed unit interval graphs, Discret. Math., 312, 3357-3363, 2012 · Zbl 1251.05037 · doi:10.1016/j.disc.2012.07.037 |
| [7] | Fishburn, PC, Interval Orders Interval Graphs, 1985, New York: Wiley, New York · Zbl 0551.06001 |
| [8] | Frankl, P.; Maehara, H., Open-interval graphs versus closed-interval graphs, Discret. Math., 63, 97-100, 1987 · Zbl 0608.05068 · doi:10.1016/0012-365X(87)90156-7 |
| [9] | Goldberg, PW; Golumbic, MC; Kaplan, H.; Shamir, R., Four strikes against physical mapping of DNA, J. Comput. Biol., 2, 139-152, 1995 · doi:10.1089/cmb.1995.2.139 |
| [10] | Golumbic, MC, Algorithmic Graph Theory and Perfect Graphs, 2004, Amsterdam: North-Holland Publishing Co., Amsterdam · Zbl 1050.05002 |
| [11] | Hell, P.; Huang, J., Interval bigraphs and Circular arc graphs, J. Graph Theory., 46, 313-327, 2004 · Zbl 1046.05066 · doi:10.1002/jgt.20006 |
| [12] | Joos, F., A characterization of mixed unit interval graphs, J. Graph Theory., 79, 267-281, 2015 · Zbl 1316.05111 · doi:10.1002/jgt.21831 |
| [13] | Lin, I.J., West, D.B.: Interval digraphs that are indifference digraphs. In: Graph Theory, Combinatorics and Algorithms (Proceedings of the Quadrennial Conference Kalamazo, MI, 1992), pp. 751-765. Wiley-Interscience (1995) · Zbl 0843.05046 |
| [14] | Müller, H., Recognizing interval digraphs and interval bigraphs in polynomial time, Discret. Appl. Math., 78, 189-205, 1997 · Zbl 0890.68103 · doi:10.1016/S0166-218X(97)00027-9 |
| [15] | Rautenbach, D.; Szwarcfiter, JL, Unit interval graphs of open and closed intervals, J. Graph Theory., 72, 418-429, 2013 · Zbl 1261.05070 · doi:10.1002/jgt.21650 |
| [16] | Sen, M.; Sanyal, BK, Indifference digraphs: a generalization of indifference graphs and semi orders, SIAM J. Disc. Math., 7, 157-165, 1994 · Zbl 0798.05025 · doi:10.1137/S0895480190177145 |
| [17] | Talon, A., Kratochvíl, J.: Completion of the mixed unit interval graphs hierarchy. J. Graph Theory, 1-15 (2017). doi:10.1002/jgt.22159 |
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.
