{"entities":{"Q1122586":{"pageid":1133335,"ns":120,"title":"Item:Q1122586","lastrevid":66174339,"modified":"2026-04-12T08:03:06Z","type":"item","id":"Q1122586","labels":{"en":{"language":"en","value":"On the chromatic number of a graph with two forbidden subgraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4106879"}},"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":"Q1122586$680BD60B-3DFB-4638-8736-54952F40AA28","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"55a4f637de1fd0320f414b31294e504c3fa5d9d6","datavalue":{"value":{"text":"On the chromatic number of a graph with two forbidden subgraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1122586$A9638155-DB1B-411F-BCEB-5F58AE343991","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"12a9b7f787b253d4548b4e018fc8fcb4293ac9a6","datavalue":{"value":"0676.05041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122586$8A818FDA-36B0-46B4-B0C9-7D288687C109","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7b6a366da515e6126c7c75875aee36293e035258","datavalue":{"value":"10.1016/0095-8956(89)90002-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122586$05FB878C-3EB5-4A54-8AF7-919680291FA7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"649dff04c2ffe41a6eb698c30ee65e3d8a893360","datavalue":{"value":{"entity-type":"item","numeric-id":759763,"id":"Q759763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122586$F8A1BC58-E6DC-4E39-AB8B-DDEE2A637AA5","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":"Q1122586$C686775C-3A20-476C-9906-EFB7E02EC226","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1122586$8E0756B6-A199-4DC5-B46B-17D829D7DCC8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"10d929b28249e05828e6d73e76f7e46758f93df7","datavalue":{"value":"A well-known result of Vizing asserts that the edge chromatic number of a graph G equals either \\(\\Delta\\) (G) or \\(\\Delta (G)+1\\) when \\(\\Delta\\) (G) is the maximum degree of G. By using Beineke's forbidden-induced-subgraph characterization of line graphs, \\textit{S. A. Choudum} [Q. J. Math., Oxf. II. Ser. 28, 257-270 (1977; Zbl 0364.05023)] restated this result as follows: If G is a simple graph whose maximum clique has d(G) vertices, then \\(\\chi\\) (G), the (vertex) chromatic number of G, is at most \\(d(G)+1\\) provided that G has no induced subgraph isomorphic to any of nine particular graphs. Choudum, Javdekar, and Kierstead sharpened this result by proving that the conclusion remains true when certain of the nine graphs are eliminated from the hypothesis. The best such result was proved by \\textit{H. A. Kierstead} [J. Comb. Theory, Ser. B 36, 156-160 (1984; Zbl 0541.05027)] who showed that \\(\\chi (G)\\leq | d(G)+1\\) provided that G has no induced subgraph isomorphic to \\(K_{1,3}\\) or \\(K_ 5-e\\). In this paper, the author proves that the same bound on \\(\\chi\\) (G) holds provided that G has no induced subgraph isomorphic to either \\(K_{1,3}\\) or the graph obtained from \\(K_ 5\\) by deleting two adjacent edges.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122586$46FA7644-07B7-415D-8491-BD9DACC6F14A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122586$19F8B31F-E219-4966-95BC-5996F3923B4D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d7ce673a9b15cfddba829b98e94e3c7bc6ff6c7d","datavalue":{"value":"4106879","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122586$25936862-BB47-413F-9488-B6D5FDCA6101","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"30da2ea40b4d429e7bf5ede64540771894011027","datavalue":{"value":"maximum clique size","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122586$0A2743BD-743D-4B3B-A9E0-8998C4FC147A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1db4e3cd8c6237e3b25098b483a3ff821c3b321","datavalue":{"value":"forbidden subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122586$A1A7E2DB-6E1C-479F-9AA0-2164A063438F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122586$E4B644BF-916A-47AB-8F7B-C00DB1DD4B9A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1bb67f5051a1ca05cadb77d1c50de8e8c2b9a63b","datavalue":{"value":{"entity-type":"item","numeric-id":580347,"id":"Q580347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122586$BA3D5E91-592F-46F9-BA21-B414FA6FC76B","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":"Q1122586$81C46F12-F4CD-4358-80C1-4EB9AA01DB39","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5c7e7bb90f1e16e1bfa8998ea761afc5b281b639","datavalue":{"value":"https://doi.org/10.1016/0095-8956(89)90002-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1122586$0DDB938E-841B-4CB1-866E-269D8EB120C3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"222bc9fd23a6984d2195345617834378532f01b5","datavalue":{"value":"W2021242070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122586$15C1192E-F764-49F6-9DF1-CD0C4FD9F52D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9df0e75e27070d34895ffb93dbbc1f2b3e73a876","datavalue":{"value":{"entity-type":"item","numeric-id":4138749,"id":"Q4138749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122586$4F88A826-3DAB-496F-99B0-FE0E5CBF6C65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"078e2373abbd1ab87290e874864f2e32f99a9726","datavalue":{"value":{"entity-type":"item","numeric-id":3880862,"id":"Q3880862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122586$B8FF1240-4E65-46DC-9714-C2CD7A4EB512","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14dbb42dd271b9303d214fe12007f5f7feafd9ac","datavalue":{"value":{"entity-type":"item","numeric-id":794661,"id":"Q794661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122586$5FE9E48B-44C8-4EC6-B628-312AA48D56B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c6574594261f18c20655bbe9510bc17ed439523","datavalue":{"value":{"entity-type":"item","numeric-id":3115603,"id":"Q3115603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122586$8309E42C-4BD5-471E-A4EB-192ED00ACB7B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76086cb1928b989751247d7e805e1f52842e9187","datavalue":{"value":{"entity-type":"item","numeric-id":1078192,"id":"Q1078192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e568e3fe48281ba16e2bd3fb4a6d0ca56e8ae34","datavalue":{"value":{"amount":"+0.8584524989128113","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":"Q1122586$7DE2BE62-DCE8-411A-BA91-B4B498F55592","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b26c956ce4a81a91cefbb2459fb043924e1d09ac","datavalue":{"value":{"entity-type":"item","numeric-id":2918532,"id":"Q2918532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"955e0870732288bf59f76f676672df7b44ba8974","datavalue":{"value":{"amount":"+0.8102151155471802","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":"Q1122586$99A5277E-2A42-46FC-B1D3-1D233959519C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7125b0367130bddf6cdaee9da4780b685db77d4b","datavalue":{"value":{"entity-type":"item","numeric-id":1422435,"id":"Q1422435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"700559e24eafc165fb66c7f7a1ac8b3a371cfb58","datavalue":{"value":{"amount":"+0.8085185885429382","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":"Q1122586$0855DF5F-57D4-4454-9850-346D45D2A9AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"563fd57637ceda418a4c67823668b2519aac0e87","datavalue":{"value":{"entity-type":"item","numeric-id":2935268,"id":"Q2935268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aec95cfdd75e9bded5b8e5a87cd0d85d35d19d9a","datavalue":{"value":{"amount":"+0.8037470579147339","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":"Q1122586$C34DB436-28AC-414C-A6DA-32EFA0AF2411","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a438ca05cfffa14e100044e28b66f6d8184f3aec","datavalue":{"value":{"entity-type":"item","numeric-id":602712,"id":"Q602712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8ec56e67c0bff270e9aab988945f0a572001b3b","datavalue":{"value":{"amount":"+0.8001678586006165","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":"Q1122586$7EAA7183-F5EE-47D2-BC2F-7474B5D807C4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the chromatic number of a graph with two forbidden subgraphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_chromatic_number_of_a_graph_with_two_forbidden_subgraphs"}}}}}