{"entities":{"Q509086":{"pageid":510853,"ns":120,"title":"Item:Q509086","lastrevid":62368737,"modified":"2026-04-11T05:36:41Z","type":"item","id":"Q509086","labels":{"en":{"language":"en","value":"An analog of Brooks' theorem for dynamic colorings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6682168"}},"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":"Q509086$FD62C470-E239-4FB4-882B-E42C0168A7FA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"26619a19789d35489ba6eeb521667e2b89f403b0","datavalue":{"value":{"text":"An analog of Brooks' theorem for dynamic colorings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q509086$6B1E5279-18AF-4842-9FCB-77E6416E8B90","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"194fc52426526843c3786f9d30bda1b0d619e52f","datavalue":{"value":"1367.05073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q509086$D7F4E9F2-23F7-4B07-A125-3DB01616C549","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0654672995e61765615aff9596caa9556e43ec97","datavalue":{"value":{"entity-type":"item","numeric-id":509085,"id":"Q509085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509086$193D25F0-B217-44DD-B829-77821CC62484","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"96d61287f253fc18075a19b52e9e24b787406c3d","datavalue":{"value":{"entity-type":"item","numeric-id":266692,"id":"Q266692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509086$7F54EE3C-37F1-43CA-9996-48B486EEB91E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0e5e5990e36b519f41dfed9405f14b12a1e45d34","datavalue":{"value":{"time":"+2017-02-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q509086$294EA238-EF51-4CB1-AE34-BF670EFE1BD0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"704d4f918350111f2ff51f3f53ca6089547e2490","datavalue":{"value":"http://mjcnt.phystech.edu/en/article.php?id=106","type":"string"},"datatype":"url"},"type":"statement","id":"Q509086$246D99CA-99D5-4E48-9BF1-C12BA49DEDFD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"54631c2787dcabe3fce3ea81769d3379a5b92472","datavalue":{"value":"The classical theorem of \\textit{R. L. Brooks} [Proc. Camb. Philos. Soc. 37, 194--197 (1941; Zbl 0027.26403)] characterizes graphs \\(G\\) whose vertices can be colored by \\(\\Delta(G)\\) colors so that adjacent vertices are colored by distinct colors, where \\(\\Delta(G)\\) denotes the maximum degree.   A (vertex) coloring of a graph is called dynamic if adjacent vertices are colored by distinct colors and for each vertex of degree at least two, the set of its neighbors is not monochromatic. This concept is a strengthening of the usual proper coloring of graphs.  This paper characterizes graphs that admits a dynamic coloring with at most \\(d\\) colors when \\(\\Delta(G)\\leq d\\) and \\(d\\geq 6\\). Namely, for \\(d\\geq 6\\), a graph of maximum degree at most \\(d\\) admits a dynamic coloring with at most \\(d\\) colors if and only if no component is isomorphic to a graph obtained from \\(K_{d}\\) by subdividing some (or no) edges once. This improves the previous result of the author for \\(d\\geq 8\\) [J. Math. Sci., New York 179, No. 5, 601--615 (2011); translation from Zap. Nauchn. Semin. POMI 381, 47--77 (2010; Zbl 1402.05070)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q509086$AA584538-BD9C-4A6B-922D-CA93B0FE13D0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e3aa5e1c84a755fa541ccb330c8402e070696732","datavalue":{"value":{"entity-type":"item","numeric-id":256976,"id":"Q256976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509086$F431A5C6-3CCE-439B-9907-7E2359AC7828","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q509086$AB62802E-C122-40BC-9435-20595128972F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2cca7772493ca69eaf995b35f299c3fe4da152f1","datavalue":{"value":"6682168","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q509086$29976F80-92A5-47FC-A456-F7A6D3F0F51D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a59ba2750774c4fe5438f914dd85e56cf4c0b57","datavalue":{"value":"proper coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q509086$48DEF9FA-B4A2-4081-B786-E15AE044EB30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"95be935caf05d156bb9cb5c9f031788955940a82","datavalue":{"value":"dynamic coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q509086$1AABF2AE-A491-4849-BDDB-C15F9FEB98FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"561e6329db45dbe88108c0aa91fc69c5266fa2f0","datavalue":{"value":"Brooks' theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q509086$AADD6765-CF24-4160-A8D6-D26ADC7E8E0D","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":"Q509086$C1BA4712-55DE-4CA2-B05C-8D03D6109C1F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb4b46778ffe7c3ef4c83c953ca94137b8ea420f","datavalue":{"value":{"entity-type":"item","numeric-id":5466088,"id":"Q5466088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3dc1fd05713d98340d615bbab6c9bf1eb73ba5e7","datavalue":{"value":{"amount":"+0.8660560846328735","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":"Q509086$1DA753B5-6A52-45AB-804B-59BC5BA07ADB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e396091694096893d418096901bec99ca28821c2","datavalue":{"value":{"entity-type":"item","numeric-id":617650,"id":"Q617650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37d5846a5834abf5ca87b908ec03916aabc7c9dc","datavalue":{"value":{"amount":"+0.8435859680175781","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":"Q509086$4B8A7A53-6337-423A-9C6B-49D67E2EE65F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f64c1cd0329ebc1ddb9421b1e34cbeba96776b0e","datavalue":{"value":{"entity-type":"item","numeric-id":2256703,"id":"Q2256703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb67bb5fa9d07050d6ee1a8b8fdaf05be4804aea","datavalue":{"value":{"amount":"+0.8393329381942749","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":"Q509086$087A13F4-F85D-4A22-BE61-E1968AD5FE38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"edb9fcd9de6e101a384aa8da7193c421915e0cb0","datavalue":{"value":{"entity-type":"item","numeric-id":2936711,"id":"Q2936711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2fcfe4e8a6534c49d6efab26330cbe7dd7d87195","datavalue":{"value":{"amount":"+0.8339173197746277","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":"Q509086$CA090962-D46B-4998-9AE2-678AD2B4E7C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20784e08a0d7fc75726f0dc4813305a41579a4ea","datavalue":{"value":{"entity-type":"item","numeric-id":967354,"id":"Q967354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16f5d278aaf258721e6bd018fb18bdd9436da784","datavalue":{"value":{"amount":"+0.8276365995407104","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":"Q509086$522E3C09-5A14-461E-85C1-EA120BA43649","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An analog of Brooks' theorem for dynamic colorings","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_analog_of_Brooks%27_theorem_for_dynamic_colorings"}}}}}