{"entities":{"Q602712":{"pageid":604488,"ns":120,"title":"Item:Q602712","lastrevid":63062031,"modified":"2026-04-11T10:16:16Z","type":"item","id":"Q602712","labels":{"en":{"language":"en","value":"Claw-free graphs. VI: Colouring"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5810779"}},"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":"Q602712$4C0A59CE-6B88-4400-8DF2-11F70B653406","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"659487a107de85a29742cdff27a25c8572d40ef5","datavalue":{"value":{"text":"Claw-free graphs. VI: Colouring","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q602712$5D8EB42D-E140-4705-A99C-B9C5EB40D756","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"656520832c30ae0fbfdb618e9705b36f8a0b5dbd","datavalue":{"value":"1207.05050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q602712$38C952E7-2DEB-4606-9027-B85BF741AA0C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"86791d2de8f741697c1a28c841b5e520b1ea6f17","datavalue":{"value":{"entity-type":"item","numeric-id":256974,"id":"Q256974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602712$313B512F-3354-4402-B6C1-8F23606923BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b7666b1aea36d852e5d73efdf8f9faa64e3f54f","datavalue":{"value":{"entity-type":"item","numeric-id":705887,"id":"Q705887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602712$FF5DC78B-9BD6-4E55-832B-6EA74368DB21","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602712$0914A4D1-9DF6-4E80-A1AE-1FEE838FCF85","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e207171999d8bccd08779f13059dd3836085b46a","datavalue":{"value":{"time":"+2010-11-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q602712$57180334-5890-4C12-8CE0-2D2AEE284177","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9ed2a4aeecf527ea6af717ded5c797c0429ace7c","datavalue":{"value":"Let \\(G\\) be a claw-free graph with independence number \\(\\alpha(G) \\geq 3\\). Then, it is shown that the chromatic number \\(\\chi(G) \\leq 2\\omega(G)\\), the clique number. This is an analogue of Vizing's Theorem for line graphs \\(H\\) of simple graphs that \\(\\chi(H) \\leq \\omega(H) + 1\\). Examples are given to show that the bound \\(2\\omega(G)\\) is sharp for \\(\\chi(G)\\), but if the condition \\(\\alpha(G) \\geq 3\\) is dropped, the bound for \\(\\chi(G)\\) is not linear in \\(\\omega(G)\\). The choice number \\(ch(G)\\), which is a list coloring number, is also considered, and it is shown that \\(ch(G) \\leq 2\\omega(G)\\) for claw-free graphs with \\(\\alpha(G) \\geq 3\\), except for possibly a special class of claw-free graphs (Schl\u00e4fli graphs, which are described in a series of articles of the authors characterizing claw-free graphs [``The structure of claw-free graphs,'' Surveys in combinatorics 2005. Papers from the 20th British combinatorial conference, University of Durham, Durham, UK, July 10--15, 2005. Cambridge: Cambridge University Press. London Mathematical Society Lecture Note Series 327, 153--171 (2005; Zbl 1109.05092); ``Claw-free graphs. I: Orientable prismatic graphs,'' J. Comb. Theory, Ser. B 97, No.\\,6, 867--903 (2007; Zbl 1128.05031); ``Claw-free graphs. II: Non-orientable prismatic graphs,'' J. Comb. Theory, Ser. B 98, No.\\,2, 249--290 (2008; Zbl 1137.05040); ``Claw-free graphs. III: Circular interval graphs,'' J. Comb. Theory, Ser. B 98, No.\\,4, 812--834 (2008; Zbl 1158.05035); ``Claw-free graphs. IV: Decomposition theorem,'' J. Comb. Theory, Ser. B 98, No.\\,5, 839--938 (2008; Zbl 1152.05038); ``Claw-free graphs. V. Global structure,'' J. Comb. Theory, Ser. B 98, No.\\,6, 1373--1410 (2008; Zbl 1196.05043)]).","type":"string"},"datatype":"string"},"type":"statement","id":"Q602712$5929ED34-94DF-4B4E-BB4B-C0E88E824F8C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"69ba710ec323ba2b1e2239c5bdd6e4165b935d93","datavalue":{"value":{"entity-type":"item","numeric-id":175582,"id":"Q175582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602712$1F97BD6D-4842-457F-8EA8-A02A82E28D7B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q602712$644D4A63-E1E0-4EFD-8F77-42F2BB724078","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q602712$8F92C937-EC63-4E0A-AC33-DD4F525A84C9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f0bdaf4353755c9ae9c15e3260e15198e6adb239","datavalue":{"value":"5810779","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q602712$01BED0B0-EB6F-4AA2-824F-2E8379ACCF1D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf2bdc388a8c2bee548ba5c2acc5f66c693118c4","datavalue":{"value":"claw-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q602712$150E353F-E327-4119-A194-A3A2F17B2B59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q602712$00571534-B91B-4519-BED4-C9122DC3F253","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f51628859d3741a7d4b3d92b1098364d202d37a4","datavalue":{"value":"choosability","type":"string"},"datatype":"string"},"type":"statement","id":"Q602712$28D2E348-169E-488C-BD6B-451524A5AD0F","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":"Q602712$6134DA5C-E1E4-420A-9A1B-AA10A9392FFB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7e80bfb9186b8b13738665410620884485a2c179","datavalue":{"value":"https://doi.org/10.1016/j.jctb.2010.04.005","type":"string"},"datatype":"url"},"type":"statement","id":"Q602712$0373DCAE-D6C5-4D61-807D-4BFE26A5B253","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5d8a21ad4212fcce397d49064d04931ea24440f1","datavalue":{"value":"W1998081086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q602712$6439A88D-A835-4F27-BF30-FFE489D0C872","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d10281a34d20d204e9c34d792af9cec706675df3","datavalue":{"value":{"entity-type":"item","numeric-id":4661935,"id":"Q4661935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602712$BA98D185-63C2-4403-AFBD-1D1CAEEAF2EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc86e16bdd50d23eac66ada42b6accdfbc1a08b7","datavalue":{"value":{"entity-type":"item","numeric-id":933683,"id":"Q933683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602712$DF44C72B-39FE-4DBA-96EC-55C4FA86E8EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae6640227334e5c106e3e971e9b01d78c1596b3c","datavalue":{"value":{"entity-type":"item","numeric-id":958695,"id":"Q958695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602712$2965C5E1-5613-4B91-A591-62C86E9E476C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3573b87026595a32002fa2dc54ac8b096bc29f3f","datavalue":{"value":{"entity-type":"item","numeric-id":3922703,"id":"Q3922703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602712$8B99D355-D1AF-4A2F-87E4-828C26E7FDEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15132b3e75729a6d081fd45a4b035add2a9fce88","datavalue":{"value":{"entity-type":"item","numeric-id":4851927,"id":"Q4851927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602712$608423D7-D543-4DD8-9411-7494DB41593D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3826395f74e3a23428a80ecf75f2bac6385da4d","datavalue":{"value":{"entity-type":"item","numeric-id":3258698,"id":"Q3258698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602712$A959E2B7-C455-4130-BBF1-00A080D218E2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3d50eb1285cbf0e5d7f43011a36845378bd333ce","datavalue":{"value":"10.1016/J.JCTB.2010.04.005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q602712$615005DD-33F6-4E7D-95B6-B23F4E5977A5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"810ffa2145336abcb75482d730b9b43a21ce5d98","datavalue":{"value":{"entity-type":"item","numeric-id":742576,"id":"Q742576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36075dc7a00bf7262abfae4baee4ce7f71134c3c","datavalue":{"value":{"amount":"+0.884812593460083","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":"Q602712$95CF08A5-F40A-4A71-83A3-A5019E653C9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77fd27d384a1afdbf61872f1a63cd0a6624f3fb7","datavalue":{"value":{"entity-type":"item","numeric-id":5346550,"id":"Q5346550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"469094091240500805d4f79ba1c5a555748ae30b","datavalue":{"value":{"amount":"+0.8375510573387146","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":"Q602712$92B8D75E-32DC-43F2-A154-94D47B45D1E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7383774fd7e7d53d763c035d665e99c054fa5e7e","datavalue":{"value":{"entity-type":"item","numeric-id":503632,"id":"Q503632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e09088801f872b3524f6f5faec4a3bc993ada31e","datavalue":{"value":{"amount":"+0.8375049233436584","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":"Q602712$11F5161C-9B95-4848-A01A-973B82A6CFF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b62f0adc7d21377018246b442a484f1619f7a86","datavalue":{"value":{"entity-type":"item","numeric-id":1356789,"id":"Q1356789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7f642c81106ffd9118ebbd5121f23ef085bfe54","datavalue":{"value":{"amount":"+0.8283122181892395","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":"Q602712$E16E697F-2B77-426F-8927-95804842A532","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ace03d11738a2e7548614cff73cfbd7a165f531e","datavalue":{"value":{"entity-type":"item","numeric-id":2631088,"id":"Q2631088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7f642c81106ffd9118ebbd5121f23ef085bfe54","datavalue":{"value":{"amount":"+0.8283122181892395","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":"Q602712$1F6A2192-873C-4783-9F89-810B2D233C48","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Claw-free graphs. VI: Colouring","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Claw-free_graphs._VI:_Colouring"}}}}}