{"entities":{"Q650874":{"pageid":652723,"ns":120,"title":"Item:Q650874","lastrevid":51382025,"modified":"2026-01-18T00:34:27Z","type":"item","id":"Q650874","labels":{"en":{"language":"en","value":"Backbone coloring of planar graphs without special circles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5986980"}},"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":"Q650874$E63708A5-B8AD-45BD-8DD7-B00FBEA1BC64","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ae702a54b197aa0c4b2ad496ca91014490761abb","datavalue":{"value":{"text":"Backbone coloring of planar graphs without special circles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q650874$B0B5F144-E0F4-4118-A782-0075D6A3CDF5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5e06ea8dc94389c2146b66d66df32f6e44901d9d","datavalue":{"value":"1230.05126","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650874$0FDB95F8-D21A-4520-BB51-C013A8FB76A8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9329971179cd1cf38774a499cf6b46db0ee9ba5e","datavalue":{"value":{"entity-type":"item","numeric-id":328714,"id":"Q328714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650874$A94498A6-FD48-443C-9229-CE5E30A38565","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8e2620669e349b0b4d6fb303f9c62dadbd200d03","datavalue":{"value":{"entity-type":"item","numeric-id":2520477,"id":"Q2520477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650874$EB048834-D5B9-4332-B488-9052B67D3972","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650874$55D410E3-6323-4BD4-8626-BB234DE1A3DD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e38c6f1e03c0365fe5e243370e140f97607764e2","datavalue":{"value":{"time":"+2011-12-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q650874$5624604B-DF8C-4827-B5FB-2EFE0F853578","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a63fc36ca093fded5e9a56e37d600b3a66817d31","datavalue":{"value":"Given a graph \\(G = (V,E)\\) and a spanning subgraph \\(H\\) of \\(G\\) (the backbone of \\(G\\)), a backbone \\(k\\)-coloring of \\((G,H)\\) is a proper vertex coloring \\(f: V \\rightarrow \\{1, 2, \\ldots, k\\}\\) of \\(G\\) such that \\(|f(u) - f(v)| \\geq 2\\) if \\(uv \\in E(H)\\) and \\(|f(u) - f(v)| \\geq 1\\) if \\(uv \\in E(G)\\setminus E(H)\\). The authors prove that any connected planar graph \\(G\\) without adjacent triangles and without chordless \\(6\\)-cycles or chordless \\(7\\)-cycles admits a spanning tree \\(T\\) such that \\((G,T)\\) has a backbone \\(4\\)-coloring. A related result [\\textit{W. Wang, Y. Bu, M. Montassier} and \\textit{A. Raspaud}, ``On backbone coloring of graphs,'' J. Comb. Optim. 23, 79--93 (2012)] is as follows: Any connected non-bipartite planar graph \\(G\\) without cycles of length less than \\(10\\) admits a spanning tree \\(T\\) such that \\((G,T)\\) has a backbone \\(4\\)-coloring.","type":"string"},"datatype":"string"},"type":"statement","id":"Q650874$D7C995F3-27CA-4BA7-BFAA-76D4FECEB236","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c4d08f81dccf0def423a8aaa09abdd52c85c61ef","datavalue":{"value":{"entity-type":"item","numeric-id":185062,"id":"Q185062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650874$292BF47A-80A2-4F7D-B8FD-A9082C3C5BD1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650874$B072A2EC-2F4E-480C-9338-96FBBFD98498","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"79961668d17b417126c490380f94947d7c77d2f0","datavalue":{"value":"5986980","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650874$4E0DC522-3EDC-4B4B-837B-7B98782889A6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba63340dc0f27f6736ca2125ce5c45f1187c56b4","datavalue":{"value":"backbone coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q650874$10B12595-805B-4BEB-8115-B48CDD2CD401","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q650874$CEEFC6B6-336B-4F14-863F-4B2B09BF488B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849b7a0d6519fee636943d9bde0b8b557d98cf60","datavalue":{"value":"spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q650874$05F9DCE8-A738-4A43-89CC-C8C1AEE2FA5D","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":"Q650874$F3239D4F-62D9-4830-AB55-5D8D2131E387","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5c97b394d677761d52cc2d9eb96b21c2630061be","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2011.06.032","type":"string"},"datatype":"url"},"type":"statement","id":"Q650874$72915506-402F-4A35-81AD-EF15AFDB3CB8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d51c32e6debb6f5d495d23a4d6bbd5700b0b3951","datavalue":{"value":"W2028290377","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650874$C55DEA39-4E85-422D-90A4-976843D667EE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650874$364E804D-98F6-4126-AAD1-D098CB053C0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"819abfe0a0e5be0d9a7bd2448759775336b2faab","datavalue":{"value":{"entity-type":"item","numeric-id":3445508,"id":"Q3445508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650874$A6E9B8B1-1575-41D6-B2B4-2E352001C8AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"039e41ed6d8d403f872172c378176f3b68e0c083","datavalue":{"value":{"entity-type":"item","numeric-id":1045046,"id":"Q1045046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650874$78640012-DB86-4759-8B94-F7D26A6E7CFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0f9399224ab4286517f11e61d70a5c204f533fa","datavalue":{"value":{"entity-type":"item","numeric-id":5324108,"id":"Q5324108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650874$9266EEF1-C633-49E4-AFAE-1D22FE220CA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16542dd068befca24e66d8e2c54b9aa9734261ee","datavalue":{"value":{"entity-type":"item","numeric-id":5902516,"id":"Q5902516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650874$6941930E-5C6A-409C-BF19-6AA0B0CA4887","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7bbdbc2a6a96d1959688cd065ed2499545a0b22","datavalue":{"value":{"entity-type":"item","numeric-id":434190,"id":"Q434190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650874$523DF031-623C-489B-B1D8-A59DC6654523","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d503a650c0c3efa45cd6258cddd19c3c2896904a","datavalue":{"value":{"entity-type":"item","numeric-id":5017648,"id":"Q5017648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650874$AE9B0544-6F82-40D7-A77A-24DC1FA1884D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4dbbd26abcca7b59632b40ced66dc5cc94d2e81e","datavalue":{"value":"10.1016/J.TCS.2011.06.032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650874$86FF0B8B-1646-486D-B0F1-780D97C5F436","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"293f035646707c5e4511c83ccb965d4ace19099f","datavalue":{"value":{"entity-type":"item","numeric-id":4926710,"id":"Q4926710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7947916c9399343537b93b25cf453f5668f3794","datavalue":{"value":{"amount":"+0.924504578113556","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":"Q650874$F3A3713A-4981-4372-8273-06B00CFF5032","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a1c6c7b198df5aa29fb8b51d1a675c069af27d4","datavalue":{"value":{"entity-type":"item","numeric-id":3193845,"id":"Q3193845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff82e10c653e6c347364d4bf63f8cc90eb479b85","datavalue":{"value":{"amount":"+0.9094988107681274","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":"Q650874$534EC972-454D-47F3-BC90-8FA87A26C3BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ff5f9e9ad52371084642dbafb8986fc0f676593","datavalue":{"value":{"entity-type":"item","numeric-id":2344770,"id":"Q2344770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31b03df1d1f23141bc4a154b3eb2964c5f120f29","datavalue":{"value":{"amount":"+0.9087318778038024","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":"Q650874$41C1CC03-BEF8-4BFF-B00B-A17E6C18EB19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71fd6053e120542b49703b26a680e99ade75c777","datavalue":{"value":{"entity-type":"item","numeric-id":5017648,"id":"Q5017648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24d723c3793e73f15f9504d8a7eb811424febbb6","datavalue":{"value":{"amount":"+0.9021871089935304","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":"Q650874$07A47B63-134B-4BAC-83B6-FB12E9D60D5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7955c454c1dc0bd69847010914d781944d5cb7df","datavalue":{"value":{"entity-type":"item","numeric-id":3110554,"id":"Q3110554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1daed8fad3fd815f73cd5c2f0eb262d8d1232e3","datavalue":{"value":{"amount":"+0.8935672640800476","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":"Q650874$DE9AF032-9D92-4AC9-838F-3072F1A5DA7A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:650874","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:650874"}}}}}