{"entities":{"Q1014829":{"pageid":1016677,"ns":120,"title":"Item:Q1014829","lastrevid":66019062,"modified":"2026-04-12T06:59:23Z","type":"item","id":"Q1014829","labels":{"en":{"language":"en","value":"On path factors of \\((3,4)\\)-biregular bigraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5549543"}},"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":"Q1014829$B8D0843F-A1AF-4E82-AE0B-F5B10828CE47","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"151d3c30f1f9df3ea67ca5af33e86d2ee7ac7f6d","datavalue":{"value":{"text":"On path factors of \\((3,4)\\)-biregular bigraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1014829$3AEE4671-76F4-4E21-A511-E2D27F59452A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e7890295c00d03d51e82f234c8767fc6159b6542","datavalue":{"value":"1177.05089","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1014829$02C7B0E9-C5DE-4D22-A56B-20E4F524A15E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d5530fc74ad38687c0397127a3799a228037b747","datavalue":{"value":{"entity-type":"item","numeric-id":1014828,"id":"Q1014828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014829$445D6E5C-9238-431F-B446-FAA0498D0A6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"03b0659dc4a395a1284d960142bd1427dea4590c","datavalue":{"value":{"entity-type":"item","numeric-id":292249,"id":"Q292249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014829$191A4449-28B5-4B59-8767-E830029AC161","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014829$0DE58117-8BF4-4F74-A319-208A4D168BA9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cc7396a377674bf1d1ad6a9c9bbfaef229fcbe16","datavalue":{"value":{"time":"+2009-04-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1014829$6AD0D5C9-9D62-4C3C-8A7F-C63E59BD6FE8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d0d42dd153dd28a67be709177bdefab45a699721","datavalue":{"value":"https://arxiv.org/abs/0706.1740","type":"string"},"datatype":"url"},"type":"statement","id":"Q1014829$6D15AF60-3E73-448C-A167-166F64EBD185","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9a3baadd9bc5181a65606a5187cde4e364657916","datavalue":{"value":"A \\((3,4)\\)-biregular bigraph \\(G\\) is a bipartite graph in which all vertices of one part have degree \\(3\\), and all vertices of the other part have degree \\(4\\). A path factor of \\(G\\) is a spanning subgraph whose connected components are paths of at least \\(2\\) vertices. The main result of the paper is to establish that any simple \\((3,4)\\)-biregular bigraph \\(G\\) admits a path factor such that the endpoints of each path have degree \\(3\\). The proof of the theorem is constructive and implies a polynomial-time algorithm for determining such a factor. It is also observed that the claim does not hold for the case when \\(G\\) is not simple, i.e., is allowed to have multiple edges.  The paper is a partial step towards settling the conjecture that every simple \\((3,4)\\)-biregular bigraph admits a factor of the considered type, with the additional property that all paths are of length at most \\(8\\). Providing a positive answer to this question would imply that the edge coloring problem always admits a feasible solution in the studied class of bigraphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1014829$FA82CF5E-A4EB-489E-AD00-7E30151EC02B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f7addfa2fd95328cb0fd319b401923622c7bf4f4","datavalue":{"value":{"entity-type":"item","numeric-id":269495,"id":"Q269495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014829$63105B13-F797-4025-923F-8CC5AC60872C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1014829$BA52AABD-6F89-4E1B-980D-08AB076BD5A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1014829$11D14A23-4C50-4738-A288-E7B495BD253F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1014829$9764469E-C884-4700-909E-21366D62E566","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3c078dffb10d736197b60830d958fe026eb08766","datavalue":{"value":"5549543","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1014829$8622AE76-EA5E-4CB2-B068-1928DCA171FD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9a557a5c9148975b0134bb53da67240234d0b609","datavalue":{"value":"path factor","type":"string"},"datatype":"string"},"type":"statement","id":"Q1014829$5EC4F5B4-B4C8-4802-AEB0-BA55831F4D89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e519ebbee9929673ca9a2c360aa5f257e0675d4e","datavalue":{"value":"biregular bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1014829$D268DECE-39AA-4E22-BA6A-E2864133C61E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e22713fcf0927b69af7b594f12e48b042aa5019b","datavalue":{"value":"interval edge coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1014829$700C136D-3A7F-462B-840B-3EE2073EBE30","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":"Q1014829$3DC46676-F441-4821-81AB-261D149EE312","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3c1527a9bd0ede0236ec43c915d36a3ae36d37de","datavalue":{"value":"W2087162634","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1014829$01446198-B287-460E-AC45-3F02A0102EBF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"44fc22c06f965499386a5630c266a934689f4add","datavalue":{"value":{"entity-type":"item","numeric-id":3714113,"id":"Q3714113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014829$0002F5F5-A8E8-4557-BB28-964C884228E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"957e01228e8c5c7bf4f223025f0f7eb926a19386","datavalue":{"value":{"entity-type":"item","numeric-id":5957707,"id":"Q5957707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014829$7090A914-E846-4DED-9B04-46CF34869768","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b1d017ac3299079efd4ef60b6355c6a820b9eb6","datavalue":{"value":{"entity-type":"item","numeric-id":882116,"id":"Q882116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014829$7F8C0539-0197-4837-AE44-2D4A7072B960","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7b78ccef29cb6d6ddd94b8c79f343448fa0f060","datavalue":{"value":{"entity-type":"item","numeric-id":3632998,"id":"Q3632998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014829$11048874-B10A-419A-A3AD-D6ECAEBC2990","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b68ec865cb7baf88f2cd7bcba9c3c7c3fbd782b","datavalue":{"value":{"entity-type":"item","numeric-id":1333322,"id":"Q1333322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014829$AB3ABB8C-5E17-4DB5-B652-AF607556D8A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77603a316f9fc5a4ef71b23813df472c259d2abf","datavalue":{"value":{"entity-type":"item","numeric-id":4208001,"id":"Q4208001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014829$87BA19A8-94C1-4FBC-A20A-B32C07396109","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"050ac9a469249e01447a5e976073451625407a32","datavalue":{"value":{"entity-type":"item","numeric-id":4430881,"id":"Q4430881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014829$C58ABD4A-4997-4822-A96C-0A93D91B9851","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea8f9edc5faa2fd277810a544fb03be621def82f","datavalue":{"value":{"entity-type":"item","numeric-id":3097395,"id":"Q3097395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014829$E65E1415-8B63-4C98-B44A-3040B16DC7BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3a31a13cd3aa5bf2a5c6c85126806cf41971a6a","datavalue":{"value":{"entity-type":"item","numeric-id":705502,"id":"Q705502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014829$F39837ED-8866-4424-BBF6-E745E1FA9C8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6eb15656b0f84ca861bb102eb04603fa36662845","datavalue":{"value":{"entity-type":"item","numeric-id":4393386,"id":"Q4393386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014829$39D344B1-F713-48FD-ACDA-58AFB3407B2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b13adfa7f4185a0eaac26e4928f0665753cb853c","datavalue":{"value":{"entity-type":"item","numeric-id":2713634,"id":"Q2713634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014829$F2167D63-C3B4-4D04-8635-DB47EC55A18D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe16c6cba2ca6dffd1e6c9cc919df6ad47736d2d","datavalue":{"value":{"entity-type":"item","numeric-id":4717033,"id":"Q4717033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014829$044696F7-66A0-4791-BDD6-49A7280AA8AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7256850b21cc9f1165b43c6f901496c1cf5c4057","datavalue":{"value":{"entity-type":"item","numeric-id":1400955,"id":"Q1400955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014829$C5FE8B47-40F0-4E70-93D0-5BA0E7D9758A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b48febe56d173c4e59597303185377ba4c7d195","datavalue":{"value":{"entity-type":"item","numeric-id":3651178,"id":"Q3651178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014829$DC0AF993-0D82-4A37-944A-800AF404D2F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15ff834b37202064387c4fc5ecec2ed8d1b82a38","datavalue":{"value":{"entity-type":"item","numeric-id":868347,"id":"Q868347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014829$E5C8ED90-BB24-4B37-B55F-7B897C478D53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bcbdf8470cc510a996cb483fa3ada32bff09a911","datavalue":{"value":{"entity-type":"item","numeric-id":3159395,"id":"Q3159395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014829$3C37E31A-84F2-4EFE-B420-099BEAFC64E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b5aa8001d12c41342658a7fc567f37d4941efd0","datavalue":{"value":{"entity-type":"item","numeric-id":4284102,"id":"Q4284102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014829$8FCAAABC-080F-4B2E-9E14-0A1A4D89BDD1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"99ca4cccfbc482002c2c8de8cca29bebf2d8f20c","datavalue":{"value":"10.1007/S00373-008-0803-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1014829$4F217AE2-46B5-42FA-A11A-35E60B85BFDA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5defc5b81790e643720a8f5f55ff04ee7393346a","datavalue":{"value":{"entity-type":"item","numeric-id":648412,"id":"Q648412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"098226d3b8b88431c1a92e90e01764f0f809a62a","datavalue":{"value":{"amount":"+0.8402339220046997","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":"Q1014829$3E9E9C67-2F80-4B61-8A44-D4AB460D571E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9ec034f283edeaf6c3e3f15e6905c4faec8de1f","datavalue":{"value":{"entity-type":"item","numeric-id":3632998,"id":"Q3632998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffee16e6c8ecc0d75398d06159ab5c84ca08384c","datavalue":{"value":{"amount":"+0.8093008399009705","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":"Q1014829$82129BF7-44A7-454B-923D-C0239A1892C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb338792471856d743cc86b6c007f29be1b79476","datavalue":{"value":{"entity-type":"item","numeric-id":2081492,"id":"Q2081492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b398498da2e21d655d401fe168c3a33f3eb23b8e","datavalue":{"value":{"amount":"+0.785831093788147","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":"Q1014829$96C85E66-B019-4B85-B862-DA6A5A6E7E6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70650a2501238fc95ad2459479b4cf6265ff7e68","datavalue":{"value":{"entity-type":"item","numeric-id":4284102,"id":"Q4284102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ee6959c3827a1d5bb38fa37bab32cb04b86d025","datavalue":{"value":{"amount":"+0.7814212441444397","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":"Q1014829$CCD46021-546C-4C35-84FB-C25B2A04E186","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85e6f3efcea8697d4dcf6381a9bf68ef535bc84b","datavalue":{"value":{"entity-type":"item","numeric-id":1117248,"id":"Q1117248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72085b362f7e9fada273044589543c7862c04680","datavalue":{"value":{"amount":"+0.7803249359130859","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":"Q1014829$4861AAAB-D9E9-41B9-B2B3-FED333BE65E0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On path factors of \\((3,4)\\)-biregular bigraphs","badges":[]}}}}}