{"entities":{"Q1801703":{"pageid":1812445,"ns":120,"title":"Item:Q1801703","lastrevid":71291700,"modified":"2026-04-13T21:15:07Z","type":"item","id":"Q1801703","labels":{"en":{"language":"en","value":"Generalizations of independence and chromatic numbers of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 205605"}},"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":"Q1801703$2B3E5247-8D04-4AF7-974A-02DEF108596B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0b3a413f1911b6701175d4e15348c2d09265581f","datavalue":{"value":{"text":"Generalizations of independence and chromatic numbers of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1801703$F1F25D3F-A599-445E-858F-B004A7DA0967","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"95948d46d83a4d83461475a7eb1d5ca118b47ed5","datavalue":{"value":"0774.05041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801703$9A7BCACE-C91F-4F97-8748-EC56078A9767","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fd3051bab4b64d26835dc0daa54c785621300446","datavalue":{"value":"10.1016/0012-365X(93)90493-D","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801703$D093ADFF-9090-484A-9C66-B676D52E82A6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"79954a74d80bb1aa10f6472835d2bccfbb8e485b","datavalue":{"value":{"entity-type":"item","numeric-id":432700,"id":"Q432700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801703$109A4687-56B4-48C1-B4FC-12692007F798","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":"Q1801703$F3828599-EDB2-4402-B881-E9BCACD5F4BA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7464544287af257c295e9b86e319f05477765b9a","datavalue":{"value":{"time":"+1993-06-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1801703$0AE27811-0E86-45BD-8D92-548EAE0AF712","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"49cbff3e1d5cc389625536a95a9a5d68db7fcc5b","datavalue":{"value":"This paper adds one more generalization of graph-coloring to the many already in the literature (see \\textit{J. I. Brown} and \\textit{D. G. Corneil} [On generalized graph colorings, J. Graph Theory 11, 87-99 (1987; Zbl 0608.05035)], for example). Given a graph \\(G\\) and an integer \\(k\\geq 2\\), a set \\(S\\) of vertices of \\(G\\) is \\(k\\)-independent (an \\(I_ k\\)-set) if the subgraph induced by any \\(k\\)-point subset of \\(S\\) is disconnected (for \\(k=2\\) this becomes the standard definition of independence). This generalization leads to the definition of the \\(k\\)-independence number of \\(G\\) as the maximum cardinality of an \\(I_ k\\)-set, an \\(I_ k\\)-coloring of \\(G\\) as a coloring of the vertices of \\(G\\) such that the set of all vertices receiving the same color is an \\(I_ k\\)-set, and the \\(k\\)- chromatic number \\(\\chi_ k(G)\\) of \\(G\\) as the minimum number of colors needed in an \\(I_ k\\)-coloring of \\(G\\). Among other generalizations of known results about independence numbers and chromatic numbers to their \\(k\\)-analogues, it is shown that for any positive integer \\(n\\) there is a \\(K_{k+1}\\)-free graph \\(G\\) with \\(\\chi_ k(G)=n\\).   A graph \\(G\\) with \\(\\chi_ k(G)=n\\) is called \\((k,n)\\)-critical (resp., \\((k,n)\\)-minimal) if removing any vertex (resp. edge) reduces the \\(k\\)- chromatic number. Some results about \\(n\\)-critical and \\(n\\)-minimal graphs are generalized to their \\(k\\)-analogues including a characterization in \\textit{B. Toft} [On critical subgraphs of color-critical graphs, Discrete Math. 7, 377-392 (1974; Zbl 0271.05112)] of \\(n\\)-critical graphs in terms of their \\((n-1)\\)-critical subgraphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1801703$A179D709-2629-459D-81F4-D0574F8D9517","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801703$D70D9E15-1E91-4BDE-8D3A-A08011ACF591","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0e816a82a16474f079cc4f045cf88e111b7476a4","datavalue":{"value":"205605","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801703$E440C65D-7ED4-4FBB-98F1-7394704451DA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1801703$C72900B5-C636-43B8-91E5-418EA15E3D0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"35a7db87f015cab82fa7554d7b6321d93849f377","datavalue":{"value":"generalized graph colorings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1801703$793525FD-1418-4758-89E7-C5FA0D117B9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7e1a96ed6ffe2ea3d9e59077ea94ebf582551c14","datavalue":{"value":"independence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1801703$848552C5-7E4E-40DE-A129-60FD58197A9D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"457b59512685cc959c2dfec1eb05d289a709afaf","datavalue":{"value":{"entity-type":"item","numeric-id":442385,"id":"Q442385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801703$8791628A-9B29-49E2-A4E7-8DBD746BD214","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":"Q1801703$CB99DB42-F447-46B2-A13E-51011C364C98","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"648e8216b0fd41fb8914a06cf09187570e434b14","datavalue":{"value":{"entity-type":"item","numeric-id":3758854,"id":"Q3758854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801703$A35A6AC5-A340-470F-9EAD-4E82163F81D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2def493c6145889772ddbfb9ee64a57941dd9a7","datavalue":{"value":{"entity-type":"item","numeric-id":3748295,"id":"Q3748295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801703$BDFC1E71-92E2-4BED-A72A-5437F321E080","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ef839ca9a2602f8e2d900fb279b3ebb73727a8c","datavalue":{"value":{"entity-type":"item","numeric-id":5560916,"id":"Q5560916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801703$77C9BB57-4A3F-4A3D-B3C9-9A90607ED416","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1962393e4cd9abd4f57d9d10b458d7bff499cd02","datavalue":{"value":{"entity-type":"item","numeric-id":5565641,"id":"Q5565641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801703$9FE6C503-4D3E-4DD6-B7B3-7550F12742E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8233d277b3ded6133706ab325d38fe3bb56ae553","datavalue":{"value":{"entity-type":"item","numeric-id":2529589,"id":"Q2529589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801703$854E104C-DBEB-4B40-8D85-A9BDD3E93204","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":"Q1801703$40E273BC-2C29-424D-B0ED-2F39CB956262","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d0c3c0703de8c7498c1e8ddecb6199c9702f15b","datavalue":{"value":{"entity-type":"item","numeric-id":3220612,"id":"Q3220612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801703$6A9EA58E-42FC-4A4A-B414-7E13470B4473","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"257bbfd90d4fb7008a5cb4b09807d037ef0eaa5a","datavalue":{"value":{"entity-type":"item","numeric-id":5668824,"id":"Q5668824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801703$D81F9DE0-38A8-4CD9-B5F2-B54CF802BF67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ae2bbd128c0328314f0cb44ba6d2131fc918aa6","datavalue":{"value":{"entity-type":"item","numeric-id":3688407,"id":"Q3688407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801703$96217447-2951-4DEE-AE82-AE9609B822CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbec8be51a4f02ec9a820a4f2027e0ce2a73952b","datavalue":{"value":{"entity-type":"item","numeric-id":3859786,"id":"Q3859786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801703$5A096927-9B01-40A4-850D-3C3F9D4270D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17a598af6ffe29ed090e79d1ef8ea62f05aa0263","datavalue":{"value":{"entity-type":"item","numeric-id":1263595,"id":"Q1263595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801703$C6EF9159-6CCD-4865-93E8-471458142309","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"779f2ad12863a733bf0d284d9407a8b122f663eb","datavalue":{"value":{"entity-type":"item","numeric-id":759160,"id":"Q759160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801703$B9F47361-22FD-4764-90CE-475F871FBD54","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b529e9320ad65a366086728b48ae95ea2f72c585","datavalue":{"value":{"entity-type":"item","numeric-id":1121899,"id":"Q1121899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5fa4044062444ec0362e8322bfc71acef86810e3","datavalue":{"value":{"amount":"+0.8217638","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1801703$365D07B5-0433-41DE-9E82-ADF87E1524AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5cec7468861e6c37e1f8ea17b415b430b6434c67","datavalue":{"value":{"entity-type":"item","numeric-id":1076033,"id":"Q1076033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b940c93eaef0b31c3efeccd64732b8e30ff9a39","datavalue":{"value":{"amount":"+0.80888337","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1801703$11C2AB42-C269-4A1A-999A-9B23F393D184","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36c7cfc9b22b8bd8f364e304b2a317d2e7d7e1bb","datavalue":{"value":{"entity-type":"item","numeric-id":3789587,"id":"Q3789587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b9325c041965d04b2cdd2416dfd1ac271ad6092","datavalue":{"value":{"amount":"+0.8084834","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1801703$0D97DA30-1872-4EA2-83B9-31698CD4AA41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28f6d39fcdbef50265fbcf1490b7fcd8cfe512dc","datavalue":{"value":{"entity-type":"item","numeric-id":3987833,"id":"Q3987833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72021a6c192c17bbe43a4e087c2e5fb792751098","datavalue":{"value":{"amount":"+0.8077676","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1801703$AE2B2847-5719-4D30-A9D5-6318989C5BB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"456531c055dd1a110256694dff1a83b0c304f165","datavalue":{"value":{"entity-type":"item","numeric-id":4294231,"id":"Q4294231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"424360a38c86070a752f6e2c0e248bc73277e441","datavalue":{"value":{"amount":"+0.7895012","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1801703$3663D4A6-3AE9-49BC-8EB8-19DE2007DED9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14e5fda50172bd7315273704461e9b4a97fa2b26","datavalue":{"value":{"entity-type":"item","numeric-id":5423113,"id":"Q5423113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4a3be22c1b5bf898260f1e13d6b46a8da9688d3","datavalue":{"value":{"amount":"+0.7881531","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1801703$17320C23-0294-4D9D-8850-47C226328EF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a04d6d72010b391cf2f34f5b3221eacd17bae51e","datavalue":{"value":{"entity-type":"item","numeric-id":5808059,"id":"Q5808059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97657ac86b3505e08944f333153aacf8786817f8","datavalue":{"value":{"amount":"+0.7878121","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1801703$2A502CA3-216B-41C7-8D77-49B542667B69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af46f4590eb692859b32e1638a4a93c845f963d2","datavalue":{"value":{"entity-type":"item","numeric-id":3068762,"id":"Q3068762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6ce4f84ca4046a11954e5091c864d3607c5826e","datavalue":{"value":{"amount":"+0.7870253","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1801703$E16DE42A-55DA-403B-832D-D7A80D325915","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46347e7c84611810de28fb0acd9d32523a1d35ee","datavalue":{"value":{"entity-type":"item","numeric-id":1897440,"id":"Q1897440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff6389722cd04b3c849fcbb73e3d0bca8bb9dc53","datavalue":{"value":{"amount":"+0.7857661","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1801703$A2D12A86-9B3C-40A2-83C9-2CF1F2208A32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0fd486004b9138649a3102b6567021cbf5904c84","datavalue":{"value":{"entity-type":"item","numeric-id":4458595,"id":"Q4458595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b038c96a9c0a3be0f6184d615189aa0f617e3fb","datavalue":{"value":{"amount":"+0.7851192","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1801703$D418F591-8734-45FB-9188-FAB54EC38A38","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Generalizations of independence and chromatic numbers of a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Generalizations_of_independence_and_chromatic_numbers_of_a_graph"}}}}}