{"entities":{"Q659728":{"pageid":661577,"ns":120,"title":"Item:Q659728","lastrevid":42627926,"modified":"2025-07-07T09:04:45Z","type":"item","id":"Q659728","labels":{"en":{"language":"en","value":"Color chain of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5999858"}},"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":"Q659728$1A9FF65C-C1BA-4F02-B8F3-CAA200F7D011","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9c29dc48096f18f156515ab1235cfab5adb2b6f6","datavalue":{"value":{"text":"Color chain of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q659728$6283A1D3-C224-4A37-AE9D-709594AB9017","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"42cbd7d223ecc945e8eedb0ea807f75cf6a6f961","datavalue":{"value":"1244.05086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659728$9D05A9EB-6A60-4733-ADF0-FA6B97666895","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b25fb647503609794231b356fa8414969903fe1a","datavalue":{"value":{"entity-type":"item","numeric-id":385135,"id":"Q385135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659728$A289151B-1FDA-4622-8DA1-09EAEBC76311","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e7c51290ab39450b9c968821abc8b76369fc2927","datavalue":{"value":{"entity-type":"item","numeric-id":514974,"id":"Q514974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659728$F82EEB18-7F44-4ED9-9B25-D3DAA1156991","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659728$97620B9A-0816-46C6-A58D-237C6144000D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a8ae18c3aa8afb0a38e8de58d984f857c905ff39","datavalue":{"value":{"time":"+2012-01-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q659728$04CEB23D-165A-467E-A550-C12D9441DF22","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e5aabd6cd6f9c328745db0ddfcb48ea0ad133017","datavalue":{"value":"The chromatic number of a graph \\(G\\) is written \\(\\chi(G)\\). A proper \\(k\\)-coloring of a graph \\(G\\) with color classes \\(V_1, \\dots, V_k\\) is a {\\parindent=6mm \\begin{itemize}\\item[-] \\(k\\)-fall coloring if each vertex in \\(V_i\\) is adjacent to at least one vertex in \\(V_j\\), \\(j\\not= i\\); the last, respectively, largest positive integer \\(k\\) for which \\(G\\) has a \\(k\\)-fall coloring is denoted by \\(\\chi_f(G)\\), respectively, \\(\\Psi_f(G)\\); \\item[-] \\(b\\)-coloring if each \\(V_i\\) has a vertex adjacent to at least one vertex in \\(V_j\\), \\(j\\not= i\\); the largest positive integer \\(k\\) for which \\(G\\) has a \\(b\\)-coloring using \\(k\\) colors is denoted by \\(\\phi(G)\\); \\item[-] partial Grundy coloring if, for each \\(2\\leq i\\leq k\\), there exists a vertex in \\(V_i\\) that is adjacent to at least one vertex in each \\(V_j\\), \\(j < i\\); the largest positive integer \\(k\\) for which \\(G\\) has a partial Grundy coloring with \\(k\\) colors is denoted by \\(\\partial\\Gamma(G)\\); \\item[-] complete coloring if the union of two color classes is not an independent set of \\(G\\); the largest positive integer \\(k\\) for which \\(G\\) has a complete coloring with \\(k\\) colors is denoted by \\(\\Psi(G)\\).   \\end{itemize}} It is clear that for any graph \\(G\\) admitting a fall coloring, \\(\\chi(G)\\leq \\chi_f(G)\\leq \\Psi_f(G)\\leq \\phi(G)\\leq \\partial\\Gamma(G)\\leq \\Psi(G)\\). The authors exhibit an infinite family of graphs \\(G\\) with a strictly increasing color chain: \\(\\chi(G)< \\chi_f(G)< \\Psi_f(G)< \\phi(G)< \\partial\\Gamma(G)< \\Psi(G)\\). The existence of such a chain was raised in [\\textit{J.E. Dunbar}, \\textit{S.M. Hedetniemi}, \\textit{S.T. Hedetniemi}, \\textit{D.P. Jacobs}, \\textit{J. Kniseley}, \\textit{R.C. Laskar}, and \\textit{D.F. Rall}, ``Fall coloring of graphs,'' J. Comb. Math. Comb. Comput. 33, 257--273 (2000); Zbl 0962.05020)]","type":"string"},"datatype":"string"},"type":"statement","id":"Q659728$95E91860-4EE9-425A-B705-99A5F77030D3","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":"Q659728$F9779D6B-4549-46F9-AF9C-26901EE9D2C6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659728$231CA34C-B3B9-453C-AE05-994B413F25C8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0c5de163b19b2667eeb83dc3f9ded0fe445e95e0","datavalue":{"value":"5999858","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659728$4C83D396-4D3D-403B-A325-70BB4F1938D3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q659728$E697F227-68FF-45D6-A5B9-716A342DF82F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fccbee54ac1defdc8b251f942ded3e3724c22a98","datavalue":{"value":"Fall chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q659728$1E5BBEA1-38D5-4F34-AE49-9EF9D61875D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba23bcf88ced62c5968209b9093d77cae373152","datavalue":{"value":"Fall achromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q659728$87A67230-65DF-422D-AD0C-FC2C7B620588","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"140bef49a7e46712250c94c1f3746d315a6508d1","datavalue":{"value":"\\(b\\)-Chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q659728$D9C0D160-373E-4682-9E1A-E2C7F4CA5C3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"76b766c7dd647153114d1c1a70bc27387e7784e2","datavalue":{"value":"Partial Grundy number and achromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q659728$AB0D7674-F859-4897-A66A-EC68E36B516F","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":"Q659728$A65424E8-B136-4669-87D0-DC4397FC2E39","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"49dd08eebc0bcc995bb6b7586562a7119a8d94ed","datavalue":{"value":"https://doi.org/10.1007/s00373-010-0989-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q659728$37B821DB-67E6-4402-BB5F-95CA6E002C8F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0ad67c616a5d39a2d8201dab1c7069847acd42aa","datavalue":{"value":"W2125677183","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659728$AA93CEFD-9A5B-47AE-BD39-B6F4DB1AED87","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"36b5ab8f23b6ceb935b59aa7b96d32ff4ad5f7d4","datavalue":{"value":{"entity-type":"item","numeric-id":2997599,"id":"Q2997599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659728$975662D0-4707-43A5-B6FC-BA8EA7FFC699","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9288a9c10fbcf867095c87792adb6a31a25a631","datavalue":{"value":{"entity-type":"item","numeric-id":4504904,"id":"Q4504904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659728$4F1CE815-7573-4F41-9929-905C9F2ED2CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d77e8fe2b7d6a2cbed2d75ce8de73c1e4faacc36","datavalue":{"value":{"entity-type":"item","numeric-id":1415544,"id":"Q1415544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659728$A4D2646F-60D5-4463-B48F-F6ADE3AA9876","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dff1b6998120ff9e6ad67c6efd96c489b7dbac09","datavalue":{"value":{"entity-type":"item","numeric-id":5591379,"id":"Q5591379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659728$29735F77-6115-4CFE-BD7E-E7E411A8FCD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8061f104280088a601db366286deefe82ac73c86","datavalue":{"value":{"entity-type":"item","numeric-id":1283791,"id":"Q1283791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659728$5D3B594B-65A1-4F39-825D-AB7A35A39814","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe74b6b9e6781c34f43b46f3a00ce17075800bdc","datavalue":{"value":{"entity-type":"item","numeric-id":1003677,"id":"Q1003677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659728$41496962-4D8C-4C9A-A63D-00A31ADA7100","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7319b77ef4409a92168ffcc64bbddde3b998ceb","datavalue":{"value":{"entity-type":"item","numeric-id":2576842,"id":"Q2576842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659728$10890964-32F3-400F-8E18-981E3246676A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"edda8157690f89c4caa40e7ee5b32e057445d075","datavalue":{"value":"10.1007/S00373-010-0989-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659728$CDF236A1-D8BE-47B5-8BB0-98EA13C37C65","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"375ede25269b0b6662b10d02d2e7a54803656dc9","datavalue":{"value":{"entity-type":"item","numeric-id":4558664,"id":"Q4558664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41f54d6cb2eea54fc16d6020050dd33230de464f","datavalue":{"value":{"amount":"+0.88441586","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q659728$E53E2BCB-72E6-4439-98FA-809D904B6A99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b18d8d2b3df29c5160980ad54c9da64591e137f","datavalue":{"value":{"entity-type":"item","numeric-id":4635974,"id":"Q4635974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f26737bd5756542c2f185aebfd0458696b84fd6","datavalue":{"value":{"amount":"+0.882536","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q659728$EFFB0673-4646-4246-BE1F-13734815C56F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00928a906317d7fd718860b524329e13e80e24c2","datavalue":{"value":{"entity-type":"item","numeric-id":3708830,"id":"Q3708830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbc7bf3ca83ee4d5cb2ec3ee647ffd15667c9841","datavalue":{"value":{"amount":"+0.8803698","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q659728$4F7D0A4C-4422-43B9-82FD-5671AB3D61BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6182bc69eb3f20ddd139ee1fa2178fd10b9cff28","datavalue":{"value":{"entity-type":"item","numeric-id":1264160,"id":"Q1264160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9faa31d4ba6151eda2d82d302fa33a18878f5d2d","datavalue":{"value":{"amount":"+0.8692813","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q659728$82809115-7EAD-4287-8FF7-C7E68D998970","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4b5c87c997676dd232c3cf17dfa108fde7303b3","datavalue":{"value":{"entity-type":"item","numeric-id":2708254,"id":"Q2708254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2e60079ce38f7cfbda1d0fbffcb347993a3b44c","datavalue":{"value":{"amount":"+0.86882997","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q659728$0A5EA1A3-67BD-4561-8216-7A8E451670EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38fd5376257e1b661972816a1bbf7306fb35d19e","datavalue":{"value":{"entity-type":"item","numeric-id":5262890,"id":"Q5262890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fdf779c22a63523f4f97af2e232637138f3f50c0","datavalue":{"value":{"amount":"+0.86547136","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q659728$109D706D-81E9-4FBE-AAF7-C754A67A08B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9207d39d55df8e03e35c2fa8e1deaddb04480cf","datavalue":{"value":{"entity-type":"item","numeric-id":5855395,"id":"Q5855395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fdf779c22a63523f4f97af2e232637138f3f50c0","datavalue":{"value":{"amount":"+0.86547136","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q659728$EADBB548-EC56-4CE8-8451-A2202C32274B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe03f715f6558d8c05015d52670926d0090c5a86","datavalue":{"value":{"entity-type":"item","numeric-id":4559905,"id":"Q4559905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2930df74193b534dbe2f1a8f0a97f9decf6b6936","datavalue":{"value":{"amount":"+0.86478","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q659728$4514E9A0-FCD5-4EF0-BCAE-9EBA5132BF5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"877aae58c70ece70ed0edc519703639fbac2a7e2","datavalue":{"value":{"entity-type":"item","numeric-id":5119831,"id":"Q5119831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d209a745fb007e7f9ed2b6304a273e880595791","datavalue":{"value":{"amount":"+0.86433357","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q659728$009F63BB-BAD2-49A7-B874-BE0358B7492F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f78e319d61f49e48ce63e874fd0be69a1f33ddc","datavalue":{"value":{"entity-type":"item","numeric-id":4500710,"id":"Q4500710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c6b277bfaa22b335cd622cf2c4d9b56d175c720","datavalue":{"value":{"amount":"+0.8638104","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q659728$E086ECA8-3C8E-4C4E-955D-C5CAAD35E00B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:659728","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:659728"}}}}}