{"entities":{"Q1974540":{"pageid":1985282,"ns":120,"title":"Item:Q1974540","lastrevid":46915629,"modified":"2025-12-25T20:36:17Z","type":"item","id":"Q1974540","labels":{"en":{"language":"en","value":"Minimal coloring and strength of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1439839"}},"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":"Q1974540$1DCDFBCF-2E63-4ED0-9483-70E516A6FE09","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f1412f217d3e129d3420e286850c9e21990ada91","datavalue":{"value":{"text":"Minimal coloring and strength of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1974540$7CDF331D-F777-41B7-A239-57177D37A786","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"624c640a146a83945772b898282f21ec45d172cb","datavalue":{"value":"0957.05041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1974540$CF07FC8A-08E7-45CE-94A8-2A1AA97E0424","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b77f18016742bdad2c632cbec35f119a59a86545","datavalue":{"value":"10.1016/S0012-365X(99)00319-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1974540$807DE2BD-7276-43D1-BD06-4FD48865C50F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a9903203a5a576d3399db5f543b1b739f4cca399","datavalue":{"value":{"entity-type":"item","numeric-id":409402,"id":"Q409402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1974540$03559FEE-F588-45D8-8FC1-617682E9559A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b201a9147711ace65c9ec13558a31d844589e0ce","datavalue":{"value":{"entity-type":"item","numeric-id":1384119,"id":"Q1384119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1974540$26EFC521-6427-477E-90DF-8CF5230B8387","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"765183fb05bfeb478e990e1c706bb2a6fa6d85f2","datavalue":{"value":{"entity-type":"item","numeric-id":1567287,"id":"Q1567287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1974540$91154E35-019D-4D73-9449-9506EA479EFD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1974540$4D9178E4-A120-406A-BBCF-DD68857B3401","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"842b2212bda6f0009051e977a4ae47e91602c98d","datavalue":{"value":{"time":"+2001-03-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1974540$E3FA028A-44C2-4B3A-A263-9F0E00E66192","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"45833603d4bf02d62948a73d034aa2c003174b58","datavalue":{"value":"A proper vertex coloring \\(c\\) of a graph \\(G\\) using colors \\(1,2,\\dots\\) is said to be minimal if \\(\\sum_{v\\in V(G)} c(v)\\) is minimum among all vertex colorings of \\(G\\). The vertex strength of \\(G\\), denoted by \\(s(G)\\), is the smallest number of colors needed to obtain a minimal coloring of \\(G\\). (The edge strength of \\(G\\), denoted by \\(s'(G)\\), is similarly defined.) The coloring number of \\(G\\), denoted by \\(\\text{col}(G)\\), is the smallest number \\(d\\) such that for some linear ordering \\(<\\) of the vertex set of \\(G\\), the back degree \\(|\\{v: v<u\\) and \\(vu\\in E(G)\\}|\\) of each vertex \\(u\\) of \\(G\\) is strictly less than \\(d\\). These notions have been studied by E. Kubicka and others in 1989-1990. In this paper, the following results are proved: (1) For any connected graph \\(G\\), \\(s(G)= \\Delta(G)+1\\) if and only if \\(G\\) is a complete graph or an odd cycle. (2) \\(s(G)\\leq [{\\text{col}(G)+ \\Delta(G)\\over 2}]\\). (3) \\(\\Delta(G)\\leq s'(G)\\leq \\Delta(G)+ 1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1974540$C92F6B38-9655-44AA-89DF-1407515D6BA1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1974540$8C7954CC-7A35-40C1-B4C1-2B30EC867334","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9511311d19238ee2f8db00bab3b17a760511dd3b","datavalue":{"value":"1439839","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1974540$91DF053D-8504-40E7-9CEE-44D4886C0E70","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85dfdbd7a975d6137b355769addaba184ea21dc4","datavalue":{"value":"vertex coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1974540$1A63868C-08B3-4605-9B60-B12D13C12190","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"42a50445c5fa60d07dbc4fc4517b96e4e72b37f8","datavalue":{"value":"vertex strength","type":"string"},"datatype":"string"},"type":"statement","id":"Q1974540$F5F7307F-9F35-46CD-BAC0-7C0853F33A6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cafd4a0578fb131a027015e9a6605f9bd9f60155","datavalue":{"value":"edge strength","type":"string"},"datatype":"string"},"type":"statement","id":"Q1974540$55D5C904-8064-4A6E-B92D-5B7FE66013B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5fb84118c511a2f29d9e1aa1fd7ab159cc59e7c6","datavalue":{"value":"coloring number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1974540$A67B8216-CF9D-4F54-A547-33F2AC9F9E89","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0dfbdb0929ddc22bcd5bd1c182b95d3875d4d630","datavalue":{"value":{"entity-type":"item","numeric-id":1164054,"id":"Q1164054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1974540$26617070-5839-49AC-80DD-50478246CABD","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":"Q1974540$57EA7528-F58E-49D7-8F53-793585ED69F9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6c17235261a7e7ce5b523f2d9dd85e34deb47362","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(99)00319-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1974540$77A9BA87-9FE8-463B-BB62-3357BF94CF62","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"52b832ecc4883423734426176eb86efb6955ec03","datavalue":{"value":"W2089342001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1974540$9585A25E-4702-445D-B767-1496BB9E8A30","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19df2cb2960484b8346c092e4c62d177d1a1a648","datavalue":{"value":{"entity-type":"item","numeric-id":853645,"id":"Q853645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f8fc1cf3032e7c2df50ae6334e1fc2b5093cca1","datavalue":{"value":{"amount":"+0.8261358141899109","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":"Q1974540$4152C85D-9614-43FA-AF25-2746FA037BB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"537547d2069af8988abe393a0c77abe805186019","datavalue":{"value":{"entity-type":"item","numeric-id":916670,"id":"Q916670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9943c6beed54f36cc1ac2d610f2793189883c1f","datavalue":{"value":{"amount":"+0.8144179582595825","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":"Q1974540$5ECAA795-97E5-468B-B684-9A251FD363CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e22c0323f7fd454fd68b8594d2e2994df84b59a5","datavalue":{"value":{"entity-type":"item","numeric-id":4719325,"id":"Q4719325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0608b2c4d8d1752f1e824935d87b690a4a638dcd","datavalue":{"value":{"amount":"+0.805042564868927","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":"Q1974540$15016F65-F7A2-4111-8CD3-E423ECA8A554","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b6d002c316cebf51433242ba1cb936afe7aba38","datavalue":{"value":{"entity-type":"item","numeric-id":967294,"id":"Q967294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"110d3b911e881a25180cadf654194b586c72b652","datavalue":{"value":{"amount":"+0.8011530637741089","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":"Q1974540$C4887C94-BD74-421F-82D6-589ABBFAD5AB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1974540","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1974540"}}}}}