{"entities":{"Q1898735":{"pageid":1909477,"ns":120,"title":"Item:Q1898735","lastrevid":69228879,"modified":"2026-04-13T05:37:15Z","type":"item","id":"Q1898735","labels":{"en":{"language":"en","value":"A characterization of some graph classes with no long holes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 798762"}},"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":"Q1898735$57166E69-A37C-4FFB-BFAC-04953F9B791A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9bdae09872cc99280cbda8a16a3ecf95105f7f3c","datavalue":{"value":{"text":"A characterization of some graph classes with no long holes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1898735$D5F043DB-A412-4B8E-9181-52C51B394196","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"338a903a59fd35e3180fd12675e78424bd535ef6","datavalue":{"value":"0842.05074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898735$7A46943E-72C9-4317-B680-9338F6D2FBCA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"556c8c83b030e0dc48d97d63f46dad396f6bd65e","datavalue":{"value":{"entity-type":"item","numeric-id":531597,"id":"Q531597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898735$3734AFCA-B93B-4F2F-99DD-E9B5716CF21E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"aaea17b454761e4e721643e7b17e8efa2dae9e33","datavalue":{"value":{"entity-type":"item","numeric-id":198206,"id":"Q198206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898735$7FFAE2B9-77B0-477B-BF76-F9851CBF728F","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":"Q1898735$CC3906CB-1C19-458E-8A41-69B68EB92988","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5252e1eb2d7b7f01858e2e508ea93d40e7d49d49","datavalue":{"value":{"time":"+1996-07-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1898735$71B41340-2714-498F-85AE-B2A169DB8524","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0dccb1f442f9c4e1b56861cad43d281c31444574","datavalue":{"value":"The authors' main result is in some way a generalization of the next two theorems.   T1 (Dirac, 1961): \\(G\\) is a triangulated graph, iff each induced subgraph \\(H\\) of \\(G\\) is a clique or has two nonadjacent simplicial vertices of \\(H\\).   T2 (Chv\u00e1tal, Rusu, 1993): A graph contains no holes, iff each of its subgraphs \\(H\\) with at least one edge contains an edge that is not middle of any chordless path \\(P_4\\) on 4 vertices in \\(H\\).   The authors study a hierarchy of graphs \\(G\\) without holes and without some antiholes (complements of holes). They receive the following theorem: A graph \\(G\\) on \\(n\\) vertices contains no holes and no antiholes with \\(i\\) vertices \\((5\\leq i\\leq k+ 1\\leq n)\\), iff for every induced subgraph \\(H\\) of \\(G\\) with at least one edge, either \\(H\\) is inseparable and has at least \\([\\mu(H)/2]\\) edges that are \\(k\\)-simplicial in \\(H\\), or \\(H\\) has two separable edges that are \\(k\\)-simplicial in \\(H\\).   A graph \\(H\\) is inseparable if its any two edges with no common vertices belong to a path on 4 vertices in \\(H\\). The number \\([\\mu(H)/2]\\) denotes the size of nontrivial connected component of a given inseparable induced subgraph \\(H\\) of \\(G\\). An edge in a graph \\(G\\) is \\(k\\)-simplicial if its vertices are not endpoints of a chordless path on \\(k\\) vertices in the complement of \\(G\\). The authors give also a corollary concerning chordal bipartite graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898735$2816E572-E9DD-4D02-B14C-8C9F4631988C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ebe4d44a08a58073803722e37fc039de15c45af0","datavalue":{"value":{"entity-type":"item","numeric-id":761465,"id":"Q761465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898735$BF254554-0B44-4C58-9A6C-36F44D0DB054","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898735$D7ED18B5-5456-436F-8AAE-BFE17A9E71AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898735$52E737A8-17A4-4E7A-AECB-AA2EB95517FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898735$0012080B-0158-481D-A15C-23E34C23E17F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9b6fb8af0db5fadfc0a4e1f039ddb2b0a3ec1505","datavalue":{"value":"798762","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898735$DF47D63E-B14A-4D6A-BE6A-8FC26FED4A0F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"113af06087d5f246cb7e7b0b3ec54d4caf83df64","datavalue":{"value":"triangulated graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898735$BB5724C8-5E48-4C4D-B0ED-D07EE4E912FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"513cac2839aa7a3ccbd3269a7e4c7baa95a8c9ce","datavalue":{"value":"simplicial vertices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898735$635D0634-D780-45E3-A1DD-0EEBA70D13C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2d87a2d2d37c555f2d6e1aeda6f7ce93354cfe73","datavalue":{"value":"holes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898735$4F7324E5-7351-4B9C-B000-297F3CFB7B7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f1991aacf1cd32946baa42a2b1b18e2af8c5ee0","datavalue":{"value":"antiholes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898735$62AB1A37-AF74-4AB3-8BED-ADCB18D723BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bae18075f3cd32065bc5bbc56ab8f1dcf9ad7aa3","datavalue":{"value":"separable edges","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898735$DD680AC8-31FC-454F-9329-A7804AB35440","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4aaaa8a20aebc13233df640115f8b0d384236cf5","datavalue":{"value":"path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898735$04C93879-A198-4A4F-AAE4-C523980D6FC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3c30e937e6d8341b49133361bd926701141d00e","datavalue":{"value":"endpoints","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898735$79320DED-5F60-49AF-8C8B-432C933A402D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f582a718272f378714c41be3f95da8bfaf560de","datavalue":{"value":"chordless path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898735$BF8A0F66-D9B5-497A-9862-C858197520C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"084e4e084e1ca9949538be78e4b85dc1d91d6889","datavalue":{"value":"chordal bipartite graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898735$C97B0877-2D2F-419D-AFE3-E87684E0CFF0","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":"Q1898735$3317F471-ECBC-4941-9FE0-122523D9411A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3d02f7cb435d2721efe9bfcb6b82e383c67b898b","datavalue":{"value":"https://doi.org/10.1006/jctb.1995.1048","type":"string"},"datatype":"url"},"type":"statement","id":"Q1898735$5C6ACBF7-6D5B-4A10-A055-2B5DE9C80905","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"47db9e21b78711e1ceeb1ba792a54611d3ad45cf","datavalue":{"value":"W2040005901","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898735$DBF2C48B-F30A-471A-8004-E06D7352DEF1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5f9d6a6152a903f9ad1792cdf46b5a214ae8dd53","datavalue":{"value":"10.1006/JCTB.1995.1048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898735$4EF08C1C-6724-4876-9E78-19D9072F367C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5cae74d04e27210fc0d1050e5d3ab18e4015c95a","datavalue":{"value":{"entity-type":"item","numeric-id":1849953,"id":"Q1849953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56e226c7c4972302aadc1dcf159902eddc1bba3e","datavalue":{"value":{"amount":"+0.8242099285125732","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":"Q1898735$8B37B7D1-E0CA-45CF-B394-49053BB350D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc20b62cb9c6b85fbe0b1784833623ce37018561","datavalue":{"value":{"entity-type":"item","numeric-id":5903942,"id":"Q5903942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56e226c7c4972302aadc1dcf159902eddc1bba3e","datavalue":{"value":{"amount":"+0.8242099285125732","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":"Q1898735$F188CB9A-7094-44CD-9BC6-114D6D40257D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5823e3df0f1a1a06d936749a9fa5581ab06458ac","datavalue":{"value":{"entity-type":"item","numeric-id":2758335,"id":"Q2758335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f71b6e3c5fb2a7c9422c42a0ca914d129ef03452","datavalue":{"value":{"amount":"+0.7937702536582947","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":"Q1898735$5CEFCEB5-C86C-4D06-83AB-9C2375502FB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a3173d29dc3f258c5b6073bae4a50520ad9a651","datavalue":{"value":{"entity-type":"item","numeric-id":5457671,"id":"Q5457671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fdeb2a2a35a68717534723fd9399969a36b5f98","datavalue":{"value":{"amount":"+0.7765663862228394","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":"Q1898735$92ED50CB-3C60-4D92-AF0D-8EB219AA2ECD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6bf5ab597323b2bb17edbd4db7c86afa5353e244","datavalue":{"value":{"entity-type":"item","numeric-id":958679,"id":"Q958679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb480f078da45b645ff0d166dee2deafdf6cc153","datavalue":{"value":{"amount":"+0.7721765637397766","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":"Q1898735$06DFB1C4-2D0A-41B5-8818-8856CE936ED0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A characterization of some graph classes with no long holes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_characterization_of_some_graph_classes_with_no_long_holes"}}}}}