{"entities":{"Q1193431":{"pageid":1204180,"ns":120,"title":"Item:Q1193431","lastrevid":66454239,"modified":"2026-04-12T10:10:52Z","type":"item","id":"Q1193431","labels":{"en":{"language":"en","value":"A charming class of perfectly orderable graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 64622"}},"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":"Q1193431$0A2F2567-F4B5-4499-918F-5E1928366F3A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6a55b8b87fbabf698c3d71817e22ddaefa7d0a98","datavalue":{"value":{"text":"A charming class of perfectly orderable graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1193431$0BADE146-5747-4764-95B6-A736E849D95E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6ccc651ef1e4c85f127f527257e403494e33b2a1","datavalue":{"value":"0776.05091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193431$2BB3ABC7-C10E-4E98-B8B0-EABF3FC5DC4A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"920dd5b60e4a3b811c5e88444eb38f3e254a3a57","datavalue":{"value":"10.1016/0012-365X(92)90348-J","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193431$964D108D-4A9A-4502-BCC8-F29DA9731FAE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7598b946dc98bf1d17807d2ef3a244f2419361f8","datavalue":{"value":{"entity-type":"item","numeric-id":234396,"id":"Q234396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193431$7BB96C47-CDBF-43BA-87D2-5F070F46C953","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec2d7eb4aa6a054061ffef53b12788916e0dba01","datavalue":{"value":{"entity-type":"item","numeric-id":222618,"id":"Q222618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193431$A5F96545-991E-4E9B-8F88-566F419125BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3e7020a54266d4b2ab3b7f83a2814036c1ab56ec","datavalue":{"value":{"entity-type":"item","numeric-id":185063,"id":"Q185063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193431$82ABC6C7-E9B8-4154-8911-16A06A52A5A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6eccd330e58db916925e9726f6d3cc506f17a2da","datavalue":{"value":{"entity-type":"item","numeric-id":442401,"id":"Q442401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193431$8BE09D0B-099C-4C14-8A9B-867DCF2D2A40","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":"Q1193431$5522E52C-373E-4574-BDA5-2335125D6399","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5fd62271fe98c7ff9916cafed51cf35315eeeb31","datavalue":{"value":{"time":"+1992-09-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1193431$E2EA31DF-F1B0-4A0F-9F74-042B0A203C95","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"49575641324b054e7b0d44c240aef762afef18ce","datavalue":{"value":"In a variety of settings (e.g. the jump number problem in the theory of posets) greedy algorithms are efficient and for important classes of objects produce optimal solutions in all cases. In this case a greedy algorithm on a linear ordering of the vertices is to produce an optimal coloring of the graph. Those graphs for which this is always so are perfectly orderable (PO) and are (V. Chv\u00e1tal) a subclass of perfect graphs. A graph is weakly triangulated (WT) if neither \\(G\\) nor its complement \\(\\overline G\\) contain an induced cycle of length 5. \\(P_ k\\) \\((C_ k)\\) denotes a chordless path (cycle) with \\(k\\) vertices. V. Chv\u00e1tal asks whether a WT-graph with no induced \\(P_ 5\\) is PO. In this paper it is demonstrated that a WT-graph with no induced \\(P_ 5\\) and \\(\\overline P_ 6\\) (or \\(P_ 6\\) and \\(\\overline P_ 5)\\) is PO by demonstrating that such graphs are charming and that charming graphs are PO. A vertex \\(v\\) of \\(G\\) is charming if it is not the endpoint of a \\(P_ 5\\) in \\(G\\) and \\(\\overline G\\) and if it does not lie on a \\(C_ 5\\) of \\(G\\). Furthermore, \\(G\\) is charming if every induced subgraph has a charming vertex. A key lemma is that \\(G\\) with a charming vertex \\(v\\) is PO if \\(G-v\\) is PO, with proof based on a result by Chv\u00e1tal: \\(G\\) is PO if it admits an obstruction-free ordering, i.e., there is not a chordless path \\(abcd\\) (as labeled) with \\(a<b\\) and \\(d<c\\). One important observation is that existence of a charming ordering (in which \\(v_ i\\) is charming in the subgraph induced by \\(\\{v_ 1,v_ 2<v_ i\\})\\) can be determined in polynomial time, which represents an NP-escape from the general problem and therefore major progress for this class certainly.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1193431$0CC852C0-EE3F-4A36-966B-74E1F15839E9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193431$D672A74A-4F79-4E2E-AD1B-643B713E8103","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193431$3975E4FB-DB60-4C67-8C0F-BCAA90E28152","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193431$11419720-A656-4982-ACA8-A8582A34E1D4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2022ab5a81e9771b664d535eae540e7ff0e719c1","datavalue":{"value":"64622","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193431$0BE2CBD3-5957-4102-97D3-80AA1D16D715","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1299386ebc4f612e1fffd660722437a77f37e1b6","datavalue":{"value":"perfectly orderable graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1193431$2FCD579F-13A4-40EA-B863-C78526BCDCC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1fc0d7b4e0514313bef02080965517bcc5ef461","datavalue":{"value":"greedy algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1193431$47EF6804-5DF1-45EF-AB1C-D8BE83D47CBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1193431$E9C75DEB-7E9F-4B3B-A082-D2680181908B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1193431$9E37630F-A935-4589-93EB-E31FFA496DE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b383a2a71d44a6efb6491228be7e7565e17312f","datavalue":{"value":"charming graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1193431$AD3C9AF9-3AB1-4780-998A-0ECF311E6BD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c656b304e98ca6f512c9e1cb8903c694d57e8cf","datavalue":{"value":"charming vertex","type":"string"},"datatype":"string"},"type":"statement","id":"Q1193431$8146B46E-E904-4BCE-BF4D-98237BB23C7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7aade890c87a6d10c447494d8641c8a767a659e5","datavalue":{"value":"charming ordering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1193431$290DE1BC-4BF2-4B64-B22C-A153AE74245F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b626688718ca3d61fce8479b1c17fa40d92d8dda","datavalue":{"value":{"entity-type":"item","numeric-id":233347,"id":"Q233347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193431$2C1F87D5-50DB-4E7B-B961-2F6D61356DFB","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":"Q1193431$26B07CF4-64CC-4397-9C6E-3555F544779B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8a74f042ba1f29a12a670ab9d659cf777707121","datavalue":{"value":{"entity-type":"item","numeric-id":798301,"id":"Q798301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193431$DC4A30B1-4C0B-47B3-8E16-59775BBFA083","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9bd269295ba877c106cd58908caf0f087a4411b","datavalue":{"value":{"entity-type":"item","numeric-id":3347930,"id":"Q3347930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193431$A5E14200-6DD7-4F36-95B1-8346E1926D0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98d84d8d1a6e846802c9d13beeae73d688fdc4b4","datavalue":{"value":{"entity-type":"item","numeric-id":3356337,"id":"Q3356337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193431$C36F5FC0-CF0D-40A8-A77E-7AA6B1FD138A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0fe6ea96ca8b0d0a6de26c3054a97527553f7f1","datavalue":{"value":{"entity-type":"item","numeric-id":686245,"id":"Q686245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193431$8E40204E-21D3-4A50-B056-8DA8FD9718B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff9d52868be71e302f41a020cd3dde1ae69f41aa","datavalue":{"value":{"entity-type":"item","numeric-id":3800062,"id":"Q3800062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193431$61871135-F24D-48D4-85BF-E69F806E705E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193431$3DEF8CE2-D0AA-48BE-A403-ADC0BD8543F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b276fdb2188dac0c4b19127d85e1049cb332b2c","datavalue":{"value":{"entity-type":"item","numeric-id":801088,"id":"Q801088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193431$AE482CBE-AC2B-4860-B2D8-08DB549312F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbc1cbf254c6eb54db676c3af43bf0720c8750ac","datavalue":{"value":{"entity-type":"item","numeric-id":3798703,"id":"Q3798703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193431$B3B1B6EB-BB6B-402B-B29E-80C2F620DDD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26b962d5ada8b5bb3c241cecf1e141991f1d8c34","datavalue":{"value":{"entity-type":"item","numeric-id":918707,"id":"Q918707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193431$06103F0C-41EA-4A0F-99EC-8265C39EBA0A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e71508847ddf428be5d2ea42294a0ef3b262f8c","datavalue":{"value":{"entity-type":"item","numeric-id":678852,"id":"Q678852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5a8662ddee17fa6a33062a340f67ff52f79acd7","datavalue":{"value":{"amount":"+0.8416628241539001","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":"Q1193431$63A12332-D590-4256-B181-B0E6D2C23B69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10ae09667ceba9715d22199702e34348eab1cc42","datavalue":{"value":{"entity-type":"item","numeric-id":3800062,"id":"Q3800062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38ddd07d64aeb4b2dc657b4bca6bf8c953b0ab14","datavalue":{"value":{"amount":"+0.8314573764801025","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":"Q1193431$92CD8C17-3C35-42F0-A595-AE6376250087","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d8c413c288f39835d9df22e010023a6fd70d06a","datavalue":{"value":{"entity-type":"item","numeric-id":1815322,"id":"Q1815322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e0af52920fed1316e934690f5d9f68ad7297cac","datavalue":{"value":{"amount":"+0.8025519847869873","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":"Q1193431$1440C2A9-07D3-4B67-B544-B9FEA9DFD1DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f48aaef422cb96624f05377dd9f254214ba8856c","datavalue":{"value":{"entity-type":"item","numeric-id":4854623,"id":"Q4854623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e0af52920fed1316e934690f5d9f68ad7297cac","datavalue":{"value":{"amount":"+0.8025519847869873","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":"Q1193431$298C3DA3-6CA1-4D1B-8DAB-1E225F3DE3AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8b5817a1a58b871578bc06d6363b498af73d03a","datavalue":{"value":{"entity-type":"item","numeric-id":5959094,"id":"Q5959094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"267d7cfffc9b151cb20d14e85e9b22a99e6b2838","datavalue":{"value":{"amount":"+0.7987540364265442","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":"Q1193431$82DFC2B4-29FA-4A3C-9AEA-FE12CAF3320B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A charming class of perfectly orderable graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_charming_class_of_perfectly_orderable_graphs"}}}}}