{"entities":{"Q5948492":{"pageid":8125294,"ns":120,"title":"Item:Q5948492","lastrevid":41974205,"modified":"2025-05-19T23:59:09Z","type":"item","id":"Q5948492","labels":{"en":{"language":"en","value":"On planar mixed hypergraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1669791"}},"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":"Q5948492$B705BAB2-30C1-46D7-9A22-F04B9265EB4A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5df088690da5030a441e1bc42548b99ca807e785","datavalue":{"value":{"text":"On planar mixed hypergraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5948492$110AF969-2CB1-4AB7-B308-B7D12D785798","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"111679ce254741cde31c95ae7483a5afdfcc882f","datavalue":{"value":"1021.05032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5948492$2B6ABCB8-2E33-4579-BB13-1CEC8C8FAA17","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0344539925c30eafc8102699adfab87d48c82922","datavalue":{"value":{"entity-type":"item","numeric-id":213911,"id":"Q213911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948492$B79D2794-7000-4167-80F7-DF8FD96A3EF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"53427ddbb10f2ef6b2b23d5d0945110660ad7953","datavalue":{"value":{"entity-type":"item","numeric-id":273100,"id":"Q273100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948492$1595FA37-A20F-425E-A17C-2E82F42ABF63","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948492$3C8F6C61-B677-470B-8B59-9BFA22EDE12C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c41960629e6801795f7680c0855722f9188b4648","datavalue":{"value":{"time":"+2001-12-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5948492$28BD31A2-0B06-4520-92A1-028663F14420","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5f7cf613121479c35299e5b3be3c7375d6baa385","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_8/Abstracts/v8i1r35.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q5948492$ABC33D29-9C0F-4E58-ADA9-8572EBCBA12D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5948492$E9450427-9F41-4ECC-90F2-2E41CA911D8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5948492$4432A9A4-AD9E-47C7-BBF2-DE94AE6D1903","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5948492$42192AAC-D504-4EA4-9C77-50C9B562FF4A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9271f16def6868f41eb79bde7d64101255aa9691","datavalue":{"value":"1669791","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5948492$97C34265-6A08-4A1A-8E29-46E16C5BA079","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"35819470afdde5a69dd49cb60f54e29aebbf19b1","datavalue":{"value":"coloring hypergraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q5948492$C49BDE9B-762C-494F-82ED-01EFF2B2C22E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93838dd0a270abea8b57ed4c7acaa275a012717b","datavalue":{"value":"planar hypergraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q5948492$488BFC93-797D-4128-BF62-8C4C3C5A91EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0702f66a584e5404a640b5544d91d365b2ee29ae","datavalue":{"value":"mixed hypergraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q5948492$353D81F3-3B06-45FA-B34B-1D865BA2D79C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5948492$CF50358F-7A4A-4C44-A7C5-ABA14ED1D85E","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":"Q5948492$861D9DF3-3857-41C9-B9C3-546ADBD08877","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73a5cc2ceeb02e61aaaa4555a164448ecaf48229","datavalue":{"value":{"entity-type":"item","numeric-id":4794372,"id":"Q4794372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff0c57062f9efbfb0d353814895a68ea0a5664e8","datavalue":{"value":{"amount":"+0.77623856","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5948492$8F76C8AB-6C65-4681-A9D0-31E7DBD5AF4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4fac6764c8e40ff77ef10d8048a0df1155202527","datavalue":{"value":{"entity-type":"item","numeric-id":1591737,"id":"Q1591737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0570bb66e58b6445a8840bc1784ed1e0973ba98","datavalue":{"value":{"amount":"+0.774287","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5948492$72CD5DEF-4995-42C2-8B35-2BDF7161ED83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6865dede24e4916a3a25659228c82a9787cb597","datavalue":{"value":{"entity-type":"item","numeric-id":1883629,"id":"Q1883629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d04776e14795b9e6ff52579b3718eb304cf09472","datavalue":{"value":{"amount":"+0.75980383","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5948492$32543D35-3D65-4A2D-926E-715DEE52D238","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"687605dc77274cde4dd9ca25be2732138385a6b5","datavalue":{"value":{"entity-type":"item","numeric-id":5245540,"id":"Q5245540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a35a48faddf8059185f2ca684310a9c6c4c4e90e","datavalue":{"value":{"amount":"+0.75315917","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5948492$E11F7E8F-FEFB-456A-A939-64499A8FD086","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7d19d32e1206071f5bff42ab6cb9b7e1da33c00","datavalue":{"value":{"entity-type":"item","numeric-id":2766689,"id":"Q2766689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f64b75cc2cc8702b8a16d124585d57e0fb92ba5a","datavalue":{"value":{"amount":"+0.75092345","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5948492$D9B7B531-63E4-4B89-A31A-711A9230EE62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07ae8c2c63daa89a6f7862dd8d525ee0039c3378","datavalue":{"value":{"entity-type":"item","numeric-id":3798696,"id":"Q3798696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"135d29dfb3bf1600b4fe933506ebc89b5a982144","datavalue":{"value":{"amount":"+0.7497991","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5948492$20234D90-9293-46AA-AD2A-9D4B4260B825","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a63a619c99f01be5ec8c83f00403a9a1928b1d6","datavalue":{"value":{"entity-type":"item","numeric-id":3509409,"id":"Q3509409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ecc8961f169760c6e706fb38ea886882d4316e05","datavalue":{"value":{"amount":"+0.74833524","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5948492$CDD8C76A-3339-40D6-AAF8-066A8545E939","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b62b9c49627b7f6b69a16987844d26a93443186","datavalue":{"value":{"entity-type":"item","numeric-id":1566139,"id":"Q1566139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42492dda893bb2a7d35699c2452b7058f1332223","datavalue":{"value":{"amount":"+0.7449677","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5948492$A7A71514-3D5A-46FD-836D-89EAA31DB170","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9382294cff22443caba3be6ff6f1cd03bfb63d7","datavalue":{"value":{"entity-type":"item","numeric-id":3439449,"id":"Q3439449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c9b89e95041661cd4a5a9a7a33f2c22244e986d","datavalue":{"value":{"amount":"+0.7438521","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5948492$A703451A-E8B4-4E10-92E2-47A8C0B678A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0f6893d2cdd31b86315c7d9e3d3863c582bdd33","datavalue":{"value":{"entity-type":"item","numeric-id":295272,"id":"Q295272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f7721a0cb78a668ed9ae1828b8df16ced6d3651","datavalue":{"value":{"amount":"+0.7423213","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5948492$809D9A2C-F08D-4EAA-8F31-608C1558AE7A","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"8cbbc66362fbf7d8d7f018c6843a594ddf6bc83d","datavalue":{"value":"bafkreigezte6zmvwkfwoz4ausror6fxtvbycuunksefl372hxiqwl33pa4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5948492$882772CD-C788-4505-A2D0-E7438ADB0BEC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"11e05eaba502c1810614850f648f7288dd2582b9","datavalue":{"value":"A mixed hypergraph consists of a vertex set \\(V\\), together with edges (that is subsets of vertices) which may be of type \\(B\\), \\(C\\) or \\(D\\). In a coloring of the vertices of a mixed hypergraph it is required that every edge of type \\(C\\) (\\(D\\)) has two vertices with a common color (with different colors), whereas edges of type \\(B\\) must meet both of these requirements. A mixed hypergraph in which every edge is of type \\(B\\) is a bihypergraph. A hypergraph is planar if its bipartite incidence graph is planar. NEWLINENEWLINENEWLINEIt is shown here that it can be determined in polynomial time if a planar mixed hypergraph has a 2-coloring, but it is NP-complete to determine if it has a 3-coloring. Furthermore it is proved that it is NP-complete to determine if a \\(3\\)-uniform planar bihypergraph has a \\(k\\)-coloring, where \\(k\\) is part of the input. The latter is established by showing that it is NP-complete to determine if a bridgeless 3-regular planar graph has a 2-factor with at least \\(k\\) components, where \\(k\\) is part of the input. The same questions with \\(k\\) fixed remain open.NEWLINENEWLINENEWLINEAnother nice result obtained here is that planar mixed hypergraphs without edges of size 2 and with at least one edge of size at least 4, have a gap-free spectrum: the existence of colorings using \\(k_1\\) and \\(k_2\\) colors respectively, forces the existence of a \\(k\\)-coloring for every \\(k_1\\leq k\\leq k_2\\). Combining a recent result of \\textit{A. A. Diwan} [J. Comb. Theory, Ser. B 84, 249-259 (2002; Zbl 1029.05123)] with results of \\textit{A. K\u00fcndgen, E. Mendelsohn} and \\textit{V. Voloshin} [Electron. J. Comb. 7, Research paper R60 (2000; Zbl 0978.05027)] it can be shown that this result holds even if there is no edge of size \\(\\geq 4\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q5948492$7234791B-5BBE-45B7-A1F7-779B9073E416","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5948492","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5948492"}}}}}