{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T15:52:06Z","timestamp":1772812326901,"version":"3.50.1"},"reference-count":35,"publisher":"Information Processing Society of Japan","issue":"0","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Information Processing"],"published-print":{"date-parts":[[2025]]},"DOI":"10.2197\/ipsjjip.33.1033","type":"journal-article","created":{"date-parts":[[2025,12,14]],"date-time":"2025-12-14T22:09:11Z","timestamp":1765750151000},"page":"1033-1041","source":"Crossref","is-referenced-by-count":1,"title":["An Upper Bound for the Permutation-representation Number of Bipartite Graphs"],"prefix":"10.2197","volume":"33","author":[{"given":"Khyodeno","family":"Mozhui","sequence":"first","affiliation":[{"name":"Department of Mathematics, Indian Institute of Technology Guwahati"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kanduru Venkata","family":"Krishna","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Indian Institute of Technology Guwahati"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1012","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"[1] Adiga, A., Bhowmick, D. and Chandran, L.S.: Boxicity and poset dimension, <i>SIAM J. Discrete Math.<\/i>, Vol.25, No.4, pp.1687-1698 (2011).","DOI":"10.1137\/100786290"},{"key":"2","doi-asserted-by":"crossref","unstructured":"[2] Baker, K.A., Fishburn, P.C. and Roberts, F.S.: Partial orders of dimension 2, <i>Networks<\/i>, Vol.2, pp.11-28 (1972).","DOI":"10.1002\/net.3230020103"},{"key":"3","unstructured":"[3] Broere, B.: <i>Word representable graphs<\/i>, Master thesis at Radbound University, Nijmegen (2018)."},{"key":"4","unstructured":"[4] Broere, B. and Zantema, H.: The <i>k<\/i>-dimensional cube is <i>k<\/i>-representable, <i>J. Autom. Lang. Comb.<\/i>, Vol.24, No.1, pp.3-12 (2019)."},{"key":"5","doi-asserted-by":"crossref","unstructured":"[5] Chandran, L.S., Francis, M.C. and Mathew, R.: Chordal bipartite graphs with high boxicity, <i>Graphs Combin.<\/i>, Vol.27, No.3, pp.353-362 (2011).","DOI":"10.1007\/s00373-011-1017-2"},{"key":"6","doi-asserted-by":"crossref","unstructured":"[6] Chaplick, S., Felsner, S., Hoffmann, U. and Wiechert, V.: Grid intersection graphs and order dimension, <i>Order<\/i>, Vol.35, No.2, pp.363-391 (2018).","DOI":"10.1007\/s11083-017-9437-0"},{"key":"7","doi-asserted-by":"crossref","unstructured":"[7] Dilworth, R.P.: A decomposition theorem for partially ordered sets, <i>Ann. Math.<\/i>, Vol.51, No.1, pp.161-166 (1950).","DOI":"10.2307\/1969503"},{"key":"8","doi-asserted-by":"crossref","unstructured":"[8] Dushnik, B. and Miller, E.W.: Partially ordered sets, <i>Amer. J. Math.<\/i>, Vol.63, pp.600-610 (1941).","DOI":"10.2307\/2371374"},{"key":"9","doi-asserted-by":"crossref","unstructured":"[9] Felsner, S.: 3-interval irreducible partially ordered sets, <i>Order<\/i>, Vol.11, No.2 (1994).","DOI":"10.1007\/BF01108596"},{"key":"10","doi-asserted-by":"crossref","unstructured":"[10] Felsner, S., Li, C.M. and Trotter, W.T.: Adjacency posets of planar graphs, <i>Discrete Math.<\/i>, Vol.310, No.5, pp.1097-1104 (2010).","DOI":"10.1016\/j.disc.2009.11.005"},{"key":"11","doi-asserted-by":"crossref","unstructured":"[11] Felsner, S., Musta\u0163\u0103, I. and Pergel, M.: The complexity of the partial order dimension problem: closing the gap, <i>SIAM J. Discrete Math.<\/i>, Vol.31, No.1, pp.172-189 (2017).","DOI":"10.1137\/15M1007720"},{"key":"12","doi-asserted-by":"crossref","unstructured":"[12] Felsner, S., Raghavan, V. and Spinrad, J.: Recognition algorithms for orders of small width and graphs of small Dilworth number, <i>Order<\/i>, Vol.20, No.4, pp.351-364 (2003).","DOI":"10.1023\/B:ORDE.0000034609.99940.fb"},{"key":"13","doi-asserted-by":"crossref","unstructured":"[13] Felsner, S., Trotter, W.T. and Wiechert, V.: The dimension of posets with planar cover graphs, <i>Graphs Combin.<\/i>, Vol.31, No.4, pp.927-939 (2015).","DOI":"10.1007\/s00373-014-1430-4"},{"key":"14","doi-asserted-by":"crossref","unstructured":"[14] Fishburn, P.C.: Intransitive indifference with unequal indifference intervals, <i>J. Mathematical Psychology<\/i>, Vol.7, pp.144-149 (1970).","DOI":"10.1016\/0022-2496(70)90062-3"},{"key":"15","doi-asserted-by":"crossref","unstructured":"[15] Glen, M., Kitaev, S. and Pyatkin, A.: On the representation number of a crown graph, <i>Discrete Appl. Math.<\/i>, Vol.244, pp.89-93 (2018).","DOI":"10.1016\/j.dam.2018.03.013"},{"key":"16","doi-asserted-by":"crossref","unstructured":"[16] Golumbic, M.C.: <i>Algorithmic graph theory and perfect graphs<\/i>, Annals of Discrete Mathematics, Vol.57, Elsevier Science B.V., Amsterdam, second edition (2004).","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"17","doi-asserted-by":"crossref","unstructured":"[17] Halld\u00f3rsson, M.M., Kitaev, S. and Pyatkin, A.: Alternation graphs, <i>Graph-theoretic Concepts in Computer Science<\/i>, Lecture Notes in Comput. Sci., Vol.6986, pp.191-202, Springer, Heidelberg (2011).","DOI":"10.1007\/978-3-642-25870-1_18"},{"key":"18","doi-asserted-by":"crossref","unstructured":"[18] Halld\u00f3rsson, M., Kitaev, S. and Pyatkin, A.: Semi-transitive orientations and word-representable graphs, <i>Discrete Appl. Math.<\/i>, Vol.201, pp.164-171 (2016).","DOI":"10.1016\/j.dam.2015.07.033"},{"key":"19","unstructured":"[19] Hiraguti, T.: On the dimension of orders, <i>Sci. Rep. Kanazawa Univ.<\/i>, Vol.4, No.1, pp.1-20 (1955)."},{"key":"20","doi-asserted-by":"crossref","unstructured":"[20] Hopcroft, J.E. and Karp, R.M.: An <i>n<\/i><sup>5\/2<\/sup> algorithm for maximum matchings in bipartite graphs, <i>SIAM J. Comput.<\/i>, Vol.2, pp.225-231 (1973).","DOI":"10.1137\/0202019"},{"key":"21","unstructured":"[21] Kimble, R.J.: Extremal problems in dimension theory for partially ordered sets, PhD Thesis, Massachusetts Institute of Technology (1973)."},{"key":"22","unstructured":"[22] Kitaev, S.: On graphs with representation number 3, <i>J. Autom. Lang. Comb.<\/i>, Vol.18, No.2, pp.97-112 (2013)."},{"key":"23","doi-asserted-by":"crossref","unstructured":"[23] Kitaev, S. and Lozin, V.: <i>Words and graphs<\/i>, Monographs in Theoretical Computer Science, An EATCS Series, Springer, Cham (2015).","DOI":"10.1007\/978-3-319-25859-1"},{"key":"24","unstructured":"[24] Kitaev, S. and Pyatkin, A.: On representable graphs, <i>J. Autom. Lang. Comb.<\/i>, Vol.13, No.1, pp.45-54 (2008)."},{"key":"25","unstructured":"[25] McConnell, R.M. and Spinrad, J.P.: Linear-time transitive orientation, <i>Proceedings Eighth Annual ACM-SIAM Symposium on Discrete Algorithms<\/i>, pp.19-25, ACM (1997)."},{"key":"26","unstructured":"[26] Mozhui, K. and Krishna, K.V.: Graphs with Permutation-Representation Number at most Three, arXiv:2307.00301 (2023)."},{"key":"27","doi-asserted-by":"crossref","unstructured":"[27] Trotter, W.T.: Dimension of the crown <i>S<sup>k<\/sup><sub>n<\/sub><\/i>, <i>Discrete Math.<\/i>, Vol.8, pp.85-103 (1974).","DOI":"10.1016\/0012-365X(74)90113-7"},{"key":"28","doi-asserted-by":"crossref","unstructured":"[28] Trotter, W.T.: Inequalities in dimension theory for posets, <i>Proc. Amer. Math. Soc.<\/i>, Vol.47, pp.311-316 (1975).","DOI":"10.1090\/S0002-9939-1975-0369192-2"},{"key":"29","unstructured":"[29] Trotter, W.T.: <i>Combinatorics and partially ordered sets: Dimension theory<\/i>, Johns Hopkins Series in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD (1992)."},{"key":"30","doi-asserted-by":"crossref","unstructured":"[30] Trotter, W.T. and Moore, J.I.: The dimension of planar posets, <i>J. Combinatorial Theory Ser. B<\/i>, Vol.22, No.1, pp.54-67 (1977).","DOI":"10.1016\/0095-8956(77)90048-X"},{"key":"31","doi-asserted-by":"crossref","unstructured":"[31] Trotter, W.T., Moore, J.I. and Sumner, D.P.: The dimension of a comparability graph, <i>Proc. Amer. Math. Soc.<\/i>, Vol.60, pp.35-38 (1977) (1976).","DOI":"10.2307\/2041106"},{"key":"32","doi-asserted-by":"crossref","unstructured":"[32] Trotter, Jr., W.T.: Stacks and splits of partially ordered sets, <i>Discrete Math.<\/i>, Vol.35, pp.229-256 (1981).","DOI":"10.1016\/0012-365X(81)90211-9"},{"key":"33","doi-asserted-by":"crossref","unstructured":"[33] Trotter, Jr., W.T. and Bogart, K.P.: On the complexity of posets, <i>Discrete Math.<\/i>, Vol.16, No.1, pp.71-82 (1976).","DOI":"10.1016\/0012-365X(76)90095-9"},{"key":"34","unstructured":"[34] West, D.B.: <i>Introduction to Graph Theory<\/i>, Prentice Hall (1996)."},{"key":"35","doi-asserted-by":"crossref","unstructured":"[35] Yannakakis, M.: The complexity of the partial order dimension problem, <i>SIAM J. Algebraic Discrete Methods<\/i>, Vol.3, No.3, pp.351-358 (1982).","DOI":"10.1137\/0603036"}],"container-title":["Journal of Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/ipsjjip\/33\/0\/33_1033\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T03:53:17Z","timestamp":1766202797000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/ipsjjip\/33\/0\/33_1033\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"references-count":35,"journal-issue":{"issue":"0","published-print":{"date-parts":[[2025]]}},"URL":"https:\/\/doi.org\/10.2197\/ipsjjip.33.1033","relation":{},"ISSN":["1882-6652"],"issn-type":[{"value":"1882-6652","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]}}}