{"entities":{"Q804601":{"pageid":806449,"ns":120,"title":"Item:Q804601","lastrevid":49504468,"modified":"2026-01-07T09:05:50Z","type":"item","id":"Q804601","labels":{"en":{"language":"en","value":"Gallai theorems for graphs, hypergraphs, and set systems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4202307"}},"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":"Q804601$12E03DCF-D113-4621-8C59-861F99D46308","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ad05716feaab402fae61badaaa35dbc49e23905c","datavalue":{"value":{"text":"Gallai theorems for graphs, hypergraphs, and set systems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q804601$94EDBC44-B4A5-442E-9E95-F001DE2C665C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e9e01d3176850f670315b3c07389b1f9561d67e3","datavalue":{"value":"0728.05050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804601$809BB3DC-BABD-4FC3-B4AC-853332731951","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4c6444d705c7f7ac8db1a53ecf43c84e6c61dec2","datavalue":{"value":"10.1016/0012-365X(88)90192-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804601$B8EB4650-5955-4D80-A190-33CF9725929D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0cd0839c3e414e2f6fde426465f6a8e2fab7644","datavalue":{"value":{"entity-type":"item","numeric-id":189720,"id":"Q189720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804601$F89EE4CC-ABBB-4C8A-8581-C8E97C2B21F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8c9d1c9ba6bd3f4aa96f0d37d0211dfaad48b281","datavalue":{"value":{"entity-type":"item","numeric-id":251500,"id":"Q251500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804601$A703107A-BB95-4C4D-89E9-51C5F4D2CCD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8e651793e9cbddc7ea2f04c3aeb4277840ea96eb","datavalue":{"value":{"entity-type":"item","numeric-id":686247,"id":"Q686247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804601$ABCDF268-1952-4B61-A417-FC88DF0AD458","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":"Q804601$5AE7CBA6-C3BF-4624-BC80-8314E2839162","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q804601$2F56B618-4431-42F6-B194-4C97E5BF459B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7bf7172cbca6cd7df5d58b9b959b7d4153760712","datavalue":{"value":"\\textit{T. Gallai} presented in [Ann. Univ. Sci. Budapest, Rolando E\u00f6tv\u00f6s, Sect. Math. 2, 133-138 (1959; Zbl 0094.361)] his now classical theorem, involving the vertex covering number \\(\\alpha_ 0\\), the vertex independence number \\(\\beta_ 0\\), the edge covering number \\(\\alpha_ 1\\), and the maximum matching (or edge independence) number \\(\\beta_ 1:\\) Theorem. For any nontrivial, connected graph \\(G=(V,E)\\) with p vertices, \\(\\alpha_ 0+\\beta_ 0=\\alpha_ 1+\\beta_ 1=p.\\)    Since then quite a large number of similar results and generalizations of this theorem have been obtained, which we will call `Gallai Theorems'. A typical Gallai theorem has the form: \\(\\alpha +\\beta =p\\), where \\(\\alpha\\) and \\(\\beta\\) are numerical maximum or minimum functions of some type defined on the class of connected graphs and p denotes the number of vertices in a graph.    This paper is an attempt to collect and unify results of this type. In particular, we present two general theorems which encompass nearly all of the existing Gallai theorems. The first theorem is based on hereditary properties of set systems, while the second is based on partition of vertices into subgraphs having treelike properties. We also present a variety of new Gallai theorems (one of which is not a corollary of either of the two above mentioned generalizations), as well as a number of other new results.","type":"string"},"datatype":"string"},"type":"statement","id":"Q804601$C8AB53CE-9EF6-4FA2-BBC8-98A82B3E92FF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804601$AE56FBFB-DFFD-4EEE-A47A-5459E0E6947A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804601$B2715D32-7CCD-461E-8D10-6521ACD9532A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804601$8D5716A6-0CD6-4CF2-A200-59A2D8B6E842","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804601$CFCA757E-5B70-46F5-B6AB-C3F2C6DDAA80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1ad1bf428b79a0176d62afa9a160b2a17f8d9ea9","datavalue":{"value":"05D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804601$CF468100-F011-476D-9894-4F4E901CA960","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"16a41880afbd8630e6acc78be050f90ea5608911","datavalue":{"value":"05A18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804601$F9D780E3-219D-4F67-93A0-3E8E8256AE57","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3f30b3e1b3f27144bccd7d7694dc7ed2e4897944","datavalue":{"value":"4202307","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804601$ACEFC5B3-1189-4769-AFD8-16A96F6E2664","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b6cb11291f98a4f101627eab8d568a1c0001050","datavalue":{"value":"vertex covering number","type":"string"},"datatype":"string"},"type":"statement","id":"Q804601$312751F5-0052-4905-8CA3-24D3941B3213","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7494c8078123721af01551838709e4ee659346ec","datavalue":{"value":"vertex independence number","type":"string"},"datatype":"string"},"type":"statement","id":"Q804601$F44A0156-CF93-4F16-BF2D-B68E3414CDA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"506b4170193e44ab748c0ef00655f2777e975018","datavalue":{"value":"edge covering number","type":"string"},"datatype":"string"},"type":"statement","id":"Q804601$EDE2DED9-8C9F-4F0E-B714-1168DE51172E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d689f4487c2943c45363692d01f4fee6018f9836","datavalue":{"value":"Gallai Theorems","type":"string"},"datatype":"string"},"type":"statement","id":"Q804601$B6C32723-12BA-4BA1-BE2A-B9A84CF99A54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ff660537c46a0ea02613438ef354efbfd3b43bd","datavalue":{"value":"hereditary properties","type":"string"},"datatype":"string"},"type":"statement","id":"Q804601$41C57C7A-EACB-4E07-A0B3-5840410BC14E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7aa0e8291e7215ee06d60ba8bedf6381e119b065","datavalue":{"value":"partition of vertices","type":"string"},"datatype":"string"},"type":"statement","id":"Q804601$974C7D8A-3604-488A-A24B-FA90281826A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e7aa9261afd174c3e2f5b7f5c7e2a299a554644","datavalue":{"value":"subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q804601$32ACFB85-5D94-4645-A4AC-CF7AE6D783CE","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":"Q804601$E111C819-C6D9-4C48-8FB3-15C018D49447","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b585dcdf59f4fe85026177ef1a61272465233d40","datavalue":{"value":{"entity-type":"item","numeric-id":3892276,"id":"Q3892276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804601$6245C5B3-0B23-4E75-96A5-82B26785B31B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f79c945ab8de49a03e4c94f42030e55878a2df1","datavalue":{"value":{"entity-type":"item","numeric-id":3270978,"id":"Q3270978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804601$5D704098-1FB0-487B-8413-252BD5851277","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6552239d4b31d05aa1d9b453a79d813eebd97482","datavalue":{"value":{"entity-type":"item","numeric-id":5187313,"id":"Q5187313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804601$C1910549-75B1-424F-B97E-437DE0F3C531","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"257bbfd90d4fb7008a5cb4b09807d037ef0eaa5a","datavalue":{"value":{"entity-type":"item","numeric-id":5668824,"id":"Q5668824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804601$816461E4-B5A0-41CD-A831-885C9776DE42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddc6d49b334f6a1f1f178370c4118f44f8aff4bf","datavalue":{"value":{"entity-type":"item","numeric-id":5654071,"id":"Q5654071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804601$64EF6959-6C27-4DC7-BC9A-4691AB6A57BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e500a8aa9b73d136fb4306fcfcfc1ac0ad90ee8","datavalue":{"value":{"entity-type":"item","numeric-id":3340900,"id":"Q3340900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804601$120FF588-9398-4736-BECE-7068091F7B7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c01a025a8cdaf223a891b7db70627b6c8bb93cce","datavalue":{"value":{"entity-type":"item","numeric-id":3816118,"id":"Q3816118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804601$832490C9-CFF7-455D-883C-E42A35EBD0C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2bb19a6b8a2ba2a1f2f658cf5a2c075dc7bd059f","datavalue":{"value":{"entity-type":"item","numeric-id":3470505,"id":"Q3470505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804601$4C5B32C2-BCFF-4AF5-9414-450E16928591","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e06668269e864f2d2b522fc6096eccfbd34c6d20","datavalue":{"value":{"entity-type":"item","numeric-id":798663,"id":"Q798663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804601$A0AB590C-DB41-411C-8265-BDD8BF082541","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a145e9342d99c0108726f7783e78bfa82f9b2fa","datavalue":{"value":{"entity-type":"item","numeric-id":3702884,"id":"Q3702884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804601$A8880F6C-F08C-487B-A67C-64389D95F517","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"054860927dbbe52f62e0734056bf286b060498a5","datavalue":{"value":{"entity-type":"item","numeric-id":3910551,"id":"Q3910551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804601$B3C721F9-5011-46FE-8C39-4FCA9DB66252","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e5b4de892d86cea68eea4fb8333a94eff4678cb","datavalue":{"value":{"entity-type":"item","numeric-id":4775897,"id":"Q4775897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804601$9715BA42-E6B3-439D-842C-AB1DBFB68712","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"292d9ed6460855a70d1deb700ef06ef4d740d9ac","datavalue":{"value":{"entity-type":"item","numeric-id":3737461,"id":"Q3737461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804601$CB1209D6-E964-4234-9A7C-840EA215E5B6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4278120fae021b48a0717e075d0736649fdf02bb","datavalue":{"value":"https://doi.org/10.1016/0012-365x(88)90192-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q804601$A68DE68B-D603-422C-B777-9456C6ADE2AD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6ed73801dbe863a26c6237760181cac966740ce0","datavalue":{"value":"W2010891937","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804601$3EDB5B76-37EF-4186-B769-2B515C7DF257","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eed5b33b6c8b01231effb68e15fc4b3bdaf70885","datavalue":{"value":{"entity-type":"item","numeric-id":4882551,"id":"Q4882551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4e47976366631d555c398b2fde0db80df444b65","datavalue":{"value":{"amount":"+0.860252857208252","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":"Q804601$72C4D08F-305A-42BC-8E16-CE457F042B51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ce75ca63687cafaff7d3260e51f4f1fbe6fb908","datavalue":{"value":{"entity-type":"item","numeric-id":798663,"id":"Q798663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b5007f4c66d5f7137eaf8fc24dfdd2f2b4cbf92","datavalue":{"value":{"amount":"+0.8593299388885498","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":"Q804601$085275ED-D7C2-4CB2-B458-333822A4D883","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"584d57eb96cb67b406e0e682d5f326a3ccafdcfd","datavalue":{"value":{"entity-type":"item","numeric-id":4430840,"id":"Q4430840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46d3d5720bcf716ecdc272a7de2cf24c97e0e844","datavalue":{"value":{"amount":"+0.8290467262268066","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":"Q804601$19FF602D-9C81-4F0A-A8C0-2CE3F88F9287","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fdbba54922295361debc6240f6d17023e958127a","datavalue":{"value":{"entity-type":"item","numeric-id":1076693,"id":"Q1076693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d64dc343f53bd0045759959063ad9dc77abf1814","datavalue":{"value":{"amount":"+0.8290466070175171","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":"Q804601$D092A85D-80FD-491F-8CAA-9D5B1617EA3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"992e1d6e19456ee4385e6ae3a3bff31a754fc2e8","datavalue":{"value":{"entity-type":"item","numeric-id":1179466,"id":"Q1179466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23b4202c36789c662ada2d2ff271f4884bee39bb","datavalue":{"value":{"amount":"+0.8144569396972656","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":"Q804601$A0D89121-B117-46C2-B363-1F040DB3AB24","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:804601","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:804601"}}}}}