{"entities":{"Q831350":{"pageid":833198,"ns":120,"title":"Item:Q831350","lastrevid":64702956,"modified":"2026-04-11T21:39:46Z","type":"item","id":"Q831350","labels":{"en":{"language":"en","value":"Square-free graphs with no induced fork"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7347104"}},"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":"Q831350$0B890D13-ACD7-4663-AFE4-7D500FFF257C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c12cd4fdd863e6dfcaa3aa1e0a71afd0d3246f2b","datavalue":{"value":{"text":"Square-free graphs with no induced fork","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q831350$6F77B48E-DBB5-4E92-ACA4-51FB80ED8DF0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"87db905b39cd71302478a50a22281419f2719738","datavalue":{"value":"1464.05146","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q831350$B9864197-011A-4E65-9008-753EEB3631BF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"990f714553668f877928f17a619bba21a2b591da","datavalue":{"value":"10.37236/9144","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q831350$83A6D352-D30A-4BE7-B590-C0F5CB081A00","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":"Q831350$E0BD6322-0808-4F62-9574-C1E50E73DEAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8ffcb0dd2a6744d126324d646018940643ff5d16","datavalue":{"value":{"entity-type":"item","numeric-id":322307,"id":"Q322307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q831350$5ED06D4F-E57D-4BE3-9ED4-BE19EC8707D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"09b9a8dca52f1f6151c204b1f73fea024818c330","datavalue":{"value":{"entity-type":"item","numeric-id":298978,"id":"Q298978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q831350$D1E2ACE0-922D-42E8-9447-4A3022AF2E61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"998b920dc31ec5527066d9b5bdef3dc3edf2e990","datavalue":{"value":{"entity-type":"item","numeric-id":831349,"id":"Q831349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q831350$DA8B5231-561B-4453-8192-DAA6A0B57066","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q831350$849AE4A6-E795-40F6-B742-23B4A525B2B4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9ed4002d7d1dae8a4df69ca0f7d26b6ca60a982d","datavalue":{"value":{"time":"+2021-05-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q831350$0D8FDAF3-9817-4D58-B508-58AFC07B9D99","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"057b2fdadb3feb81afce286921cc06955749285e","datavalue":{"value":"Summary: The claw is the graph \\(K_{1,3}\\), and the fork is the graph obtained from the claw \\(K_{1,3}\\) by subdividing one of its edges once. In this paper, we prove a structure theorem for the class of (claw, \\(C_4)\\)-free graphs that are not quasi-line graphs, and a structure theorem for the class of (fork, \\(C_4)\\)-free graphs that uses the class of (claw, \\(C_4)\\)-free graphs as a basic class. Finally, we show that every (fork, \\(C_4\\))-free graph \\(G\\) satisfies \\(\\chi(G)\\leqslant \\bigg\\lceil\\frac{3\\omega(G)}{2}\\bigg\\rceil\\) via these structure theorems with some additional work on coloring basic classes.","type":"string"},"datatype":"string"},"type":"statement","id":"Q831350$05723197-509E-4426-9064-5B32FC1F109A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q831350$4AD8E7D7-D54D-4455-A91A-BF9C4431428C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q831350$9EA89CB0-8FD5-4C95-89B3-09CA7A41C395","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d48948dd15f0e94e222ea439976ae3a122efe7cb","datavalue":{"value":"7347104","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q831350$F6AF1A4A-AB33-49EF-8DC8-661B2F5D1238","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b6fac036d0386461048e4af513ab5529434c4260","datavalue":{"value":"forbidden induced subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q831350$A200859F-984F-45F0-9010-A37AD74DE00D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd343ce6a1acf8af90d05014300c248e5d897ba8","datavalue":{"value":"graph structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q831350$02D6FE73-47E9-4641-A689-26D8F4C7E309","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"013b5738b0b5ec995d63d7b64f81b69a1b3a8a60","datavalue":{"value":"fork","type":"string"},"datatype":"string"},"type":"statement","id":"Q831350$BEDA78CF-1A7F-471D-B7EF-B007E3A6B0C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fe5ebb8cd18c5b66df78c65d4669c5017c5fcc0c","datavalue":{"value":"antifork","type":"string"},"datatype":"string"},"type":"statement","id":"Q831350$D7E21334-C2C7-471B-B0E4-7C79522DCABA","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":"Q831350$D5C9B41C-6E4A-431C-92C8-C3950AC937C6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a5ae744460850fd80fca0ced6450dd46ba75e68f","datavalue":{"value":"https://doi.org/10.37236/9144","type":"string"},"datatype":"url"},"type":"statement","id":"Q831350$0E7F9942-2D98-46EC-B724-FCA030B5F444","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5dee97da7ca15b258d026c95aedaeb1c41b68f6e","datavalue":{"value":"W3157320200","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q831350$BDC39141-BD70-4B96-857D-12CEEF2F0C03","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f31a64d481612b78c59ae4f9174ace2118957856","datavalue":{"value":{"entity-type":"item","numeric-id":1634757,"id":"Q1634757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q831350$C594E84A-88AD-4DE8-A25B-730AC009F0F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aba8f589f4b62a8ef1bb40a6d77b249686763033","datavalue":{"value":{"entity-type":"item","numeric-id":2305900,"id":"Q2305900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q831350$36226E8B-A0B0-4EC7-8D36-EEC145C9BDE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ed1518a73cbceb6460589ac460a969fb60a595c","datavalue":{"value":{"entity-type":"item","numeric-id":3418732,"id":"Q3418732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q831350$629306EB-00AC-4A9A-9918-12F3388005DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54c40f5e287ce342e31e29db5c0eab02e99343e0","datavalue":{"value":{"entity-type":"item","numeric-id":3416248,"id":"Q3416248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q831350$E8752C0A-5E16-4801-B4F2-0DC827464845","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e577a492d50dbe28643626fd19a147b17bbf6b19","datavalue":{"value":{"entity-type":"item","numeric-id":602712,"id":"Q602712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q831350$F2102B92-660C-4A75-A541-B741FC2748DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecea865227114740eed2d5859f102d9f3a0ca075","datavalue":{"value":{"entity-type":"item","numeric-id":5749319,"id":"Q5749319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q831350$5B2D8B91-0B80-454A-8F6E-ACEB17F87E99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f50bb37b38bae24ae5cc706d9f93c054251453a1","datavalue":{"value":{"entity-type":"item","numeric-id":4284098,"id":"Q4284098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q831350$DA4D194A-5FD2-4FC9-B651-A9DCDE509B4A","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":"Q831350$E8DD8907-DDF9-410B-8CF4-EA96E9314C7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8dc8e3a70353874ae71b2b5e055e522ed5b6378c","datavalue":{"value":{"entity-type":"item","numeric-id":5847741,"id":"Q5847741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q831350$19371745-B070-4201-B4E6-4C63C01F49BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"961551c5665512b67a21d966b3640e6a34d12524","datavalue":{"value":{"entity-type":"item","numeric-id":1889838,"id":"Q1889838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q831350$56153C50-518F-4329-8A61-BB316F27A7C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38a1643a3f55fd10ed31ef36d7cba0e5d3b84f16","datavalue":{"value":{"entity-type":"item","numeric-id":3932997,"id":"Q3932997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q831350$0D9E4CA7-B628-425C-B263-90611B71C67E","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"50612207927777ea5f1e23761aa925a359d90e6d","datavalue":{"value":"bafkreidxqcx6qh3blgqmenagbtkake36ybydphkqaqckkzmw4rujuxeuyi","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q831350$B9431DD5-BED4-4A7A-B57E-7515DEC7D352","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99a2d194dc2b15e4a3d7ab5074514e6e788e0ca7","datavalue":{"value":{"entity-type":"item","numeric-id":2161205,"id":"Q2161205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38b052b828d64aa4826ca46a1a42ba12b0a0c6e4","datavalue":{"value":{"amount":"+0.826085090637207","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":"Q831350$C9ABF9F0-5692-4060-B32F-20DFDF979A99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b71c952944509790b6df39c71c19cb5982e380c7","datavalue":{"value":{"entity-type":"item","numeric-id":2994411,"id":"Q2994411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c48a5f2a03286d01eb76161c4d405061ca759c7b","datavalue":{"value":{"amount":"+0.8252761960029602","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":"Q831350$2A183020-D499-4F8B-9C21-A1D472A150A1","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":"77d2c9ceb311284031b20dc4fcc0a6539047bffe","datavalue":{"value":{"amount":"+0.8241965174674988","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":"Q831350$E07CC524-C187-445C-B595-A6257212043E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71ccc842fe8414ce06b434a9be4182f5b4abcdc5","datavalue":{"value":{"entity-type":"item","numeric-id":2305900,"id":"Q2305900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed6be051ff31d20f7b59d56cd5a1ef4a81a3da89","datavalue":{"value":{"amount":"+0.8138761520385742","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":"Q831350$73AD30FB-6FCD-407E-BDEC-F033C972142B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a25f07114603314be347cecd9e16b047a6174ad","datavalue":{"value":{"entity-type":"item","numeric-id":3025205,"id":"Q3025205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1513933731c9bcfa274be81e0788a1814440cccf","datavalue":{"value":{"amount":"+0.7823430299758911","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":"Q831350$78D7AACF-032B-4016-8FC4-8CDA0B5DA19B","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q831350$4C129614-FFAD-49DD-95F3-782D201E3D6A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Square-free graphs with no induced fork","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Square-free_graphs_with_no_induced_fork"}}}}}