{"entities":{"Q1898338":{"pageid":1909080,"ns":120,"title":"Item:Q1898338","lastrevid":71105337,"modified":"2026-04-13T19:31:16Z","type":"item","id":"Q1898338","labels":{"en":{"language":"en","value":"Searching for acyclic orientations of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 797068"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898338$2C995E87-3373-4AB2-B3FF-1AB160339BF6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8b2c1923ea394419b62498fd6be6c886b2d13f65","datavalue":{"value":{"text":"Searching for acyclic orientations of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1898338$92B93112-6BB8-4EFB-9CCD-7F7A8F0E4F14","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"19892050039d52326c92b545d6f0877d22a9bbd7","datavalue":{"value":"0831.05033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898338$6A28029F-4385-422D-AFD9-8B3B74D140D0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"22fc15cab84fae2f2511f61b423a0f638ec0a1f0","datavalue":{"value":"10.1016/0012-365X(94)00281-M","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898338$D25990E2-F42E-4752-BA4D-8D58043E8FA6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"289d49a761dfac02c62be4b7f68381ebc5e52ce3","datavalue":{"value":{"entity-type":"item","numeric-id":495333,"id":"Q495333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898338$C31E8238-F428-4581-93A0-62C22B26C609","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3f608b3eb8b967f499e211b27ac20bd2aaaca99c","datavalue":{"value":{"entity-type":"item","numeric-id":213186,"id":"Q213186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898338$376AC944-E8E8-47C3-86AD-FFE8708F2B7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"17fcd7139afa5567c823530fba22122acb06092a","datavalue":{"value":{"entity-type":"item","numeric-id":175498,"id":"Q175498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898338$83261DE0-5B12-4A07-B6C5-12B84B16A53F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898338$58402E69-5AA3-489C-ACE9-2F1D26EC74B5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7afdf265c9170445571c22ac16ade7e21534dd96","datavalue":{"value":{"time":"+1996-02-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1898338$8EBE729F-000E-4849-8811-F5ED28A94638","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e649dc2b0e4923187f38ac4dea8e51ca15116326","datavalue":{"value":"For an undirected graph \\(G\\), \\(c(G)\\) is defined to be the minimum integer \\(k\\) with the property that there exists a subgraph \\(H\\) of \\(G\\) with \\(k\\) edges such that, no matter how \\(H\\) is acyclically oriented, this orientation can be extended uniquely to an acyclic orientation of all edges of \\(G\\). The number of acyclic orientations of \\(G\\) is denoted by \\(a (G)\\); the maximum number of independent vertices is denoted by \\(\\alpha (G)\\). A graph \\(G \\) is exhaustive if \\(c(G) = |E (G) |\\). Theorem 2. For all graphs \\(G\\) on \\(n\\) vertices,  \\[ n \\log_2 {n \\over \\alpha (G)} - n \\log_2e+ {1 \\over 2} (2 + \\log_2n) < c(G) < \\alpha (G) n \\left (\\log_2 {n \\over \\alpha (G)} + 1 \\right). \\]  This permits an answer to an orally communicated question of P. Erd\u00f6s: Corollary 3. If \\((\\begin{smallmatrix} n \\\\ 2 \\end{smallmatrix}) - |E(G) |= o(n^2)\\), then \\(c(G) = o(n^2)\\) as \\(n \\to \\infty\\). For every \\(0 < \\varepsilon < {1 \\over 2}\\) there is a \\(\\delta > 0\\) such that, for large \\(n\\), there exists a graph \\(G\\) on \\(n\\) vertices with at least \\(({1 \\over 2} - \\varepsilon) n^2\\) edges, satisfying \\(c(G) \\geq \\delta n^2\\). A theorem of \\textit{J. Ne\u0161et\u0159il} and \\textit{V. R\u00f6dl} [On a probabilistic graph-theoretical method, Proc. Am. Math. Soc. 72, 417-421 (1978; Zbl 0399.05007)] is generalized: Theorem 8. For each natural number \\(s\\), there exists a nonexhaustive graph with girth at least \\(s\\). The authors acknowledge that N. Alon and Zs. Tuza have proved that the line graphs of cubic triangle-free graphs need not be exhaustive. The size of an exhaustive graph is bounded: Theorem 10. (i) For all \\(n \\geq 6\\), the number of edges in an exhaustive graph on \\(n\\) vertices is at most \\(\\lfloor {n^2 \\over 4} \\rfloor\\). (ii) For all \\(n \\geq 7\\), the complete bipartite graph \\(K_{\\lfloor {n \\over 2}\\rfloor, \\lfloor {n \\over 2} \\rfloor}\\) is the only exhaustive graph with \\(\\lfloor {n^2 \\over 4} \\rfloor\\) edges. The paper concludes with two open problems: What is the complexity status of deciding whether \\(c(G) \\leq k\\) for a given graph \\(G\\) and natural number \\(k\\)? Is it true that \\(c(G) \\leq {n^2 \\over 4} + o(n^2)\\) as \\(n \\to \\infty\\)?","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898338$998EFF33-4207-411E-9045-1728B6E0797B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898338$1B739E96-AE50-4543-BBE0-A727F7898FA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898338$B4B5C35B-6273-4864-8EFB-E80F4B2A9B2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898338$663F5EEB-9468-473B-94AF-688D8E44CAFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898338$7A5FDF0F-6FD6-452A-ACF9-5EBC3959F719","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ca0f45c7bff128fcce5765a4b44c38f436df2b5d","datavalue":{"value":"797068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898338$E4BA8E29-5B70-47D7-878A-465191810097","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"458f12def83c1367a32fd7e7e1dd4b0d57985296","datavalue":{"value":"orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898338$7C470DF0-7B60-43F6-BFEE-543743C96139","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f53979ab3dea69b6cad1df9e8205c99a9878960","datavalue":{"value":"acyclic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898338$6830D0A1-54D9-41E0-BB0F-AD3BB45A0D4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"511ef16394ff3a4942789aca793cc5a1b0857fad","datavalue":{"value":"independent vertices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898338$B362B6E9-058E-4970-B336-8148A2B9769C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b8e1643cbaae61fa069ff42f125c76fb002fac49","datavalue":{"value":"exhaustive graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898338$FBBE3766-37BB-4C27-87A7-632C0DDB87DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4ef5a98087326b7b6ae23e1778e62561b3757de","datavalue":{"value":"problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898338$02264FC7-ACC7-41A9-B4B8-61CDCF948ECC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898338$C72B67DD-7B26-4C69-A539-0CE0616E882B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7d410aa128a8b8a63913c9594604f4ec3d0ad8b4","datavalue":{"value":{"entity-type":"item","numeric-id":590664,"id":"Q590664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898338$76AB4E19-FB31-4BC9-B8CB-7AF53EC4F9D7","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898338$8E2FAE1A-75B1-42B5-82FE-F525B391B59B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a6895403b2ec68a5532c9e0a01e18b56805c593","datavalue":{"value":{"entity-type":"item","numeric-id":3994535,"id":"Q3994535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898338$E88821F9-967C-4404-B876-1E2FCBDFC6DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72bdc200c096a90cb093d01083b69c58672a0aa3","datavalue":{"value":{"entity-type":"item","numeric-id":3682518,"id":"Q3682518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898338$127A690F-B92A-4890-96EE-46478D2CCECB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cb6d330b0ba17ea9706ff485bd2cc7e5caf6771","datavalue":{"value":{"entity-type":"item","numeric-id":3883524,"id":"Q3883524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898338$FBF7C720-EF14-45AD-8226-D3899F1D9E3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8bad490746f3d137c8fc2d3faa8fba778e2c1116","datavalue":{"value":{"entity-type":"item","numeric-id":3283482,"id":"Q3283482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898338$767659E0-4F72-48E2-A028-3E208E9E307C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898338$CEB909B5-DDE7-411E-9EFF-7092D2558E3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66aa54bfb7a43ef696f12a804d0d05acf1a4d555","datavalue":{"value":{"entity-type":"item","numeric-id":3706485,"id":"Q3706485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898338$469433CE-B266-4B0D-82C5-AA9C7580125B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c07fb145c190b934a8c9134d7ebb9e5f3699a07e","datavalue":{"value":{"entity-type":"item","numeric-id":3730017,"id":"Q3730017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898338$BE0D923B-99DC-4F86-B88B-4236B447DFE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a3e770ee75376f4cc53272c6f2ca696e7e9ea87","datavalue":{"value":{"entity-type":"item","numeric-id":4182520,"id":"Q4182520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898338$C63A8249-7E2A-4394-8EA7-04597AF63C7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ee3056b1d3ab2c41b26ebc84850e169c465121d","datavalue":{"value":{"entity-type":"item","numeric-id":3726174,"id":"Q3726174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898338$2E0555CD-4DC3-451C-8C34-B4766D041181","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2aa74053b99e4e74b3e4ed9742e7abbebc0d543d","datavalue":{"value":{"entity-type":"item","numeric-id":2559389,"id":"Q2559389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898338$B0FC0745-D5D0-4FA2-AC20-6529B5DF9528","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0869e031e7758a5d3b4155645adeaf38ecb9c108","datavalue":{"value":{"entity-type":"item","numeric-id":4285000,"id":"Q4285000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26509e7f43bf07f77ac2b69e18ed2f3642bcdbb3","datavalue":{"value":{"amount":"+0.7539449334144592","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898338$749951DD-E565-4B6E-8E69-06E073B482E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b94d3aa57ebf8d72938a68b8a10d3a5ee736d679","datavalue":{"value":{"entity-type":"item","numeric-id":3129826,"id":"Q3129826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81a3144884b654ee28e5e670a8935033f18f8ea9","datavalue":{"value":{"amount":"+0.7538017630577087","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898338$7EEF0462-7148-4CF6-AF4D-F35CF61F96D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"290c3c4caa8ff59aca7a77bf50003223663a7ad8","datavalue":{"value":{"entity-type":"item","numeric-id":4697816,"id":"Q4697816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30855be22c285b2fbc556e613a4a2c631a4d02fa","datavalue":{"value":{"amount":"+0.7501622438430786","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898338$057521A3-D736-45A7-B898-8B0D79116DD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7ab5962d131ddfc88eecdde898ba4de44929a3d","datavalue":{"value":{"entity-type":"item","numeric-id":3977081,"id":"Q3977081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26e80dc3b6526ae5b5a37a83ee2d0ecfcb0b7877","datavalue":{"value":{"amount":"+0.7466409206390381","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898338$B213D963-24B1-4C85-8516-446B6E430292","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d42f8a5ef3ba9737c7fe4219e0cbec2de80d4a8","datavalue":{"value":{"entity-type":"item","numeric-id":1621059,"id":"Q1621059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06e936c574bd0f6494527a680f59e7e7812830c8","datavalue":{"value":{"amount":"+0.7434316873550415","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898338$15AD2F33-8F5C-48EE-B603-B924AA04FD4D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Searching for acyclic orientations of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Searching_for_acyclic_orientations_of_graphs"}}}}}