{"entities":{"Q1186166":{"pageid":1196915,"ns":120,"title":"Item:Q1186166","lastrevid":47061352,"modified":"2025-12-31T13:30:25Z","type":"item","id":"Q1186166","labels":{"en":{"language":"en","value":"Edge colouring line graphs of unicyclic graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 36296"}},"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":"Q1186166$AB3D5875-5FDB-41BA-8D63-65FE6CFC9735","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7dbf5c2b038e85941991c1a4721df7a8842593ae","datavalue":{"value":{"text":"Edge colouring line graphs of unicyclic graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1186166$49EA1513-4519-4736-ABC6-D21AC760223A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e49ab8f055bbb44711f405b553573825a56ede5a","datavalue":{"value":"0751.05037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186166$90DC2952-829B-4BA2-85FF-451C1F01B745","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6dc5230fae58bda1ff54e345e54450f321619b10","datavalue":{"value":"10.1016/0166-218X(92)90206-P","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186166$1E654CEA-F9CC-464C-B344-725E3A6AF4A9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f00237d5739b07662cb51e9e957100249e47b2d2","datavalue":{"value":{"entity-type":"item","numeric-id":175508,"id":"Q175508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186166$8352CED7-9BB4-482B-B491-A02C33CDD80A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cf3bc49c57fe0ee7c0f7246623770a8a8677c29d","datavalue":{"value":{"entity-type":"item","numeric-id":1173976,"id":"Q1173976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186166$A9A68FAC-4EB3-42FC-89D1-4D98E3D7B0F6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186166$10DF0D6E-3A19-4544-B68E-A34286AB45DC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1186166$9C4A3C49-46AE-4FE0-9699-A27324D36BF7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"599a45409faf4a3647e66095d3894a99ca44cbc5","datavalue":{"value":"A characterization of line graphs of unicyclic graphs is established, and it is proved that the line graph \\(G\\) of a unicyclic graph is in class 1 unless \\(G\\) is an odd cycle and an optimal edge colouring of the line graph of a unicyclic graph can be computed in time \\(O(| E|)\\) (note that the chromatic index problem is known to be \\(NP\\)-complete, even for line graphs). The results are easily extended to line graphs of graphs in which no two cycles have vertices in common.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186166$0CB8A96E-61A4-4652-8421-34A2CC856566","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186166$7C55AEB2-4D51-47D0-AB46-1FE016C96BB8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8274f0bd643954f69de066c340a02b47c9bc483c","datavalue":{"value":"36296","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186166$D09E7BE8-E69F-496A-A397-AD0894384F3C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e3d58b5f68ae7d6337620e7d25da0081273ed23","datavalue":{"value":"edge colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186166$82796D0E-EFF8-44C6-88A7-E47E412266E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e77b229532a8249bff86420a515b82c08ef4fb3","datavalue":{"value":"line graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186166$8515FFCA-390E-4F3B-9778-5B4B1CAF03EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"04c2298e8ca5e0389e53a6ec173c0db3beac97ff","datavalue":{"value":"unicyclic graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186166$4925930C-BA10-4F54-A469-0DE20A62AC77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c27a8414208eba22b391b2c3a982e6e5e1d84b","datavalue":{"value":"linear time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186166$B822B0CD-E7ED-4775-AB90-B1DB2BAEC296","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186166$DBACC444-8194-4A7D-AC39-48CA1B403BB0","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":"Q1186166$767A6D89-441B-4D1A-B851-2F6F068703B0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfb631b8675362aaf7bfdbd557e2bfc2ad8cb210","datavalue":{"value":{"entity-type":"item","numeric-id":1173977,"id":"Q1173977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186166$51AF8A90-6BDF-4730-B4C2-AF763992B483","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d1474ad965005531fc787ddda571bd10843eacd","datavalue":{"value":{"entity-type":"item","numeric-id":3853641,"id":"Q3853641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186166$44B83B87-18D4-46FB-BAA1-4AA1DA29127C","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":"Q1186166$17C69ACB-7667-4DD3-B292-EDF5A6678B38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631200adace0f14c2f6d92fc47cb2d9f5d82cdbb","datavalue":{"value":{"entity-type":"item","numeric-id":3928241,"id":"Q3928241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186166$C5065A58-B6AF-4A24-975F-091479799C20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db0285625f074a48cd1908122f2f7d851fdd299e","datavalue":{"value":{"entity-type":"item","numeric-id":3747723,"id":"Q3747723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186166$BF0E6F76-9393-455A-88CC-C1E94AE21891","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c5200a3d79bea878bb3f1f1a63dd2799adadfaf","datavalue":{"value":{"entity-type":"item","numeric-id":5903516,"id":"Q5903516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186166$AE6AEFE3-92B5-416E-8FB2-6AF63E70B971","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c45a4e0e9e90ddbbdf2661b0a0f25bfac714ad60","datavalue":{"value":{"entity-type":"item","numeric-id":3325753,"id":"Q3325753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4cf2c517c0982fbc49898f5c4e4149e39f63db7d","datavalue":{"value":{"amount":"+0.8230413794517517","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":"Q1186166$BB6A2EF0-9858-4C4E-B9C5-3A07F42DEB65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de50f3ab626e1d7eeb75ff6420fafc7be5b39657","datavalue":{"value":{"entity-type":"item","numeric-id":2267844,"id":"Q2267844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cc126d752c457d6b1680f416eb8b7486b27f238","datavalue":{"value":{"amount":"+0.7743701934814453","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":"Q1186166$12BFFF48-50CD-4B9E-82CB-25EFD91EFCC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a86f9779a31b6c71f4c3aed1ef98319b1ec6ec20","datavalue":{"value":{"entity-type":"item","numeric-id":2174556,"id":"Q2174556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9830f19944fa8d53a67f740d61d05011bcd7e16c","datavalue":{"value":{"amount":"+0.768837034702301","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":"Q1186166$C5198545-C5BC-4324-8A15-98F45C0ADA56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4e0328ef41a069ae01e7b2bdd8f392b5b052c5b","datavalue":{"value":{"entity-type":"item","numeric-id":5264742,"id":"Q5264742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ddb54ca41e79d91b67796fd815ace17d798131b","datavalue":{"value":{"amount":"+0.7584048509597778","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":"Q1186166$48A6C12F-CE54-4D10-81E8-599095EC5637","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72974ef9144553417a4bc9fa7cb9ee2b5cf8b945","datavalue":{"value":{"entity-type":"item","numeric-id":4566359,"id":"Q4566359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f29a62bdcd5427b47edfb382756b1d6f1d6ae5a5","datavalue":{"value":{"amount":"+0.757402241230011","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":"Q1186166$A89AE78F-BBB4-4DF9-815A-CC5B77DDDF9E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1186166","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1186166"}}}}}