{"entities":{"Q925035":{"pageid":926883,"ns":120,"title":"Item:Q925035","lastrevid":50368553,"modified":"2026-01-13T22:01:55Z","type":"item","id":"Q925035","labels":{"en":{"language":"en","value":"On forbidden subdivision characterizations of graph classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5280770"}},"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":"Q925035$A0C3425C-E93E-4987-96EB-508BE4F379F5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"389f2d8717942c9ba8ce7dcfdc9760e72ec7d039","datavalue":{"value":{"text":"On forbidden subdivision characterizations of graph classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q925035$4D721473-3EBD-4953-A67E-DAE1BF2F30B5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0c2f47c26ab683271f4044a1adcf9de887f5458d","datavalue":{"value":"1151.05038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925035$809EADB3-4155-432D-85C2-7C1DDCCACC2D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0344539925c30eafc8102699adfab87d48c82922","datavalue":{"value":{"entity-type":"item","numeric-id":213911,"id":"Q213911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925035$71FC7F35-C98E-4226-86D1-38DBCCC815C6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925035$AA605559-254D-452E-81B5-C943D93A3C8F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6d5ea9744be37dbc33ed76d7f80e76e9dbefcded","datavalue":{"value":{"time":"+2008-05-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q925035$90F54FA9-1BA6-432A-98B4-84BD523F6196","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"32cd0fe7f16818b0c622e644dd7051f2ebff0833","datavalue":{"value":"Let \\(G\\) be a simple undirected graph. A graph \\(G'= G^{(t)}\\) is the \\(t\\)-subdivision of \\(G\\) if \\(G'\\) is obtained from \\(G\\) by replacing each edge by a path with exactly \\(t\\) internal vertices. Similarly, \\(G'\\) is a \\(\\leq t\\)-subdivision of \\(G\\) if \\(G'\\) can be obtained from \\(G\\) by subdividing each edge by at most \\(t\\) vertices. The number of vertices may be different for each edge. A coloring of the vertices of \\(G\\) is proper if no two adjacent vertices have the same color. The minimum \\(k\\) such that \\(G\\) has a proper coloring by \\(k\\) colors is called the chromatic number of \\(G\\), denoted \\(\\chi(G)\\). A proper coloring of \\(G\\) is acyclic if the union of each two color classes induces a forest, i.e., there is no cycle colored by two colors. The minimum \\(k\\) such that \\(G\\) has an acyclic coloring by \\(k\\) colors is called the acyclic chromatic number of \\(G\\), denoted \\(\\chi_a(G)\\). The acyclic chromatic number of a graph is also related to several other graph parameters, as, for example, the arrangeability, the greatest reduced average density, the game chromatic number and a sequence of parameters related to the expansion of a graph. The author gives an exact characterization of graph classes whose acyclic chromatic number is bounded by a constant. Analogous characterizations are given for some of the above-mentioned parameters.","type":"string"},"datatype":"string"},"type":"statement","id":"Q925035$BBE4E18B-E02A-4592-953F-75C1EDFFFB4B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925035$DFCF3583-425C-4945-AB83-B143B9CBE37E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925035$119DF5B8-FC20-4AB9-99F1-500042C32BD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925035$CFC0F7DD-CFE0-46B9-A78F-D3D0A1E54F21","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"636f4876ee4cd91fcd7ad815b927c734ef7d6266","datavalue":{"value":"5280770","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925035$0FB80772-172A-4B67-8DD5-224C122C1B1D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c286c794aad43de599a522f7c4a8e1fd6623f6c","datavalue":{"value":"\\(t\\)-subdivision","type":"string"},"datatype":"string"},"type":"statement","id":"Q925035$559337D1-F195-4911-BFCD-F2C3C764E625","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f7ff947e235867ef720d4550c13fd0dd3943856","datavalue":{"value":"acyclic proper coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q925035$A2C41D0D-FB72-4984-AADC-01E5EBB96B42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0356c2e27890491bf2eb295bab1472565bcd67b7","datavalue":{"value":"acyclic chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q925035$4B00DEA9-5C78-4566-AF03-3698E2D807CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aa0189bdf901462b65a7c8237c9b1a4c3236a617","datavalue":{"value":"arrangeability","type":"string"},"datatype":"string"},"type":"statement","id":"Q925035$23C6E1F7-30E0-4D76-B0DC-4DF8F06776A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcfba89c4564e67a77a6f8e4dc251b20694557c0","datavalue":{"value":"greatest reduced average density","type":"string"},"datatype":"string"},"type":"statement","id":"Q925035$1E959DB8-2163-40B6-9A9C-A0BA822D7D8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a963503414bb31a41fdec1c5970580fc87536736","datavalue":{"value":"game chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q925035$2023A678-E8B1-437F-86EF-E4966A21095F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8aa823381996fcc0ccd3a2cba10b758f14d14704","datavalue":{"value":"graph classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q925035$B225B434-C6F2-418F-9564-AA4B8DB49791","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f3cea8802bf5eb5583a41701b0e21b11c7abe658","datavalue":{"value":{"entity-type":"item","numeric-id":288052,"id":"Q288052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925035$DD654BD2-4F5B-494F-8252-E6D3BBD93215","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":"Q925035$2B51185A-6BCC-4986-920D-AAB6FC73A3E8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"606e6325c20acf4f16dc4463a606014721bf8382","datavalue":{"value":"https://doi.org/10.1016/j.ejc.2007.05.008","type":"string"},"datatype":"url"},"type":"statement","id":"Q925035$8A392998-EA3A-44B3-89D6-626A741EAFA9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"894bc74ad75e48aa2f5bc70799c44caabaab4484","datavalue":{"value":"W2118815975","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925035$37F3FC71-B325-4C40-8D30-B3FF8691B74B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2c1115e87dc51532b4feca2a675e0421662ac53","datavalue":{"value":{"entity-type":"item","numeric-id":1883636,"id":"Q1883636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925035$BE03926F-94AD-4DDA-BB58-8A1B719BB67B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9208528a9398d42022a83d3910fdcc8477ab6c6","datavalue":{"value":{"entity-type":"item","numeric-id":2784326,"id":"Q2784326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925035$2F35E34A-8ED5-4776-9EE8-A59A2469712A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f92dd856ac6e85d46c013684d1de479b1f38df9f","datavalue":{"value":{"entity-type":"item","numeric-id":1257487,"id":"Q1257487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925035$F7125C58-DDC1-4437-8BA9-91AFCF370EBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3413111f26c2d678b27e34447dbc7636ebebde7","datavalue":{"value":{"entity-type":"item","numeric-id":2277497,"id":"Q2277497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925035$6575CE59-7811-4E26-A8E3-67555B21842A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"941517d17c41c64f7b62f7eb9b2b332972f75dfc","datavalue":{"value":{"entity-type":"item","numeric-id":1297403,"id":"Q1297403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925035$53C7BDB7-CEAF-4D23-8361-87044BF841BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55b9e664dcc8ea5ef8123282c3afcecea1b5f55f","datavalue":{"value":{"entity-type":"item","numeric-id":4116466,"id":"Q4116466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925035$653C7383-5533-413F-BE82-B1F25B98D4BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac40c6cf68874e578148471cf13e5477b00b1532","datavalue":{"value":{"entity-type":"item","numeric-id":5692719,"id":"Q5692719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925035$AA7D2233-381D-44CA-B0F6-54BB2F088E27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6013dc0a8096d83b98502cbe1fb7f9f602b20466","datavalue":{"value":{"entity-type":"item","numeric-id":1039442,"id":"Q1039442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925035$074862CD-FDFE-4341-8D7D-3F20B0B7F398","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d639d539a34bd9f2eadace636bc10b6d7599ff3","datavalue":{"value":{"entity-type":"item","numeric-id":2426456,"id":"Q2426456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925035$2CA885CD-E9FA-4DCC-A5EC-193BD3076827","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6d71e8e9e23e8ccf7fd49dc162cd1febeeeb202","datavalue":{"value":{"entity-type":"item","numeric-id":2426457,"id":"Q2426457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925035$2DB4AAD9-0000-4FAA-AE97-F491C023A86D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d14e6d90b116aabcb304713f4f55aaa0ce47db3","datavalue":{"value":{"entity-type":"item","numeric-id":2427548,"id":"Q2427548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925035$1F350EDC-8E0E-4042-9265-42815F3E60AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb7340c7e4bad066830d41cd30e631c015cc0e46","datavalue":{"value":{"entity-type":"item","numeric-id":4309985,"id":"Q4309985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925035$862789AC-4316-4A00-A3BC-7921E08A16E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74c25e4752494ba376f6774236f3dc27008b0ae4","datavalue":{"value":{"entity-type":"item","numeric-id":1826511,"id":"Q1826511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925035$0D05808F-EC05-4A5D-A30E-61B1CE36A0A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"298443ffdafb0525e60ab4966dd8ce2a9d6e4508","datavalue":{"value":{"entity-type":"item","numeric-id":4194980,"id":"Q4194980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925035$E382900B-AA0A-43A1-B3D5-5A797933C246","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a8af05808f6f01472797ba96e638baeb86e8678","datavalue":{"value":{"entity-type":"item","numeric-id":5689012,"id":"Q5689012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925035$F683330F-0A7B-4886-BCF1-B4C760BAF4EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98b8762e5e74279b3614c47cf1fe1d3d47885cbf","datavalue":{"value":{"entity-type":"item","numeric-id":4667626,"id":"Q4667626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925035$CD6CC716-02EA-4FD7-9CB1-2C777F8AAE5E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f4f308042d4251aae8a68fbcf827021171ac1304","datavalue":{"value":"10.1016/J.EJC.2007.05.008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925035$D095EC5D-927F-4CB0-91C9-513B74392DED","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4ced0643993917fe4b92ea7559f0f929d579ab3","datavalue":{"value":{"entity-type":"item","numeric-id":1686256,"id":"Q1686256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16b8cecd30b9b4590cdbbf2c944005ca6eb1f577","datavalue":{"value":{"amount":"+0.7328141331672668","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":"Q925035$A23CB949-D4F8-4D52-B35E-11807BE5E00A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1398f4cdbad713298b5e606d57b67b5b7053acfe","datavalue":{"value":{"entity-type":"item","numeric-id":3826590,"id":"Q3826590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"177441d9fdfed7bdb469e3ddcccbf3e8fcd965be","datavalue":{"value":{"amount":"+0.7318835854530334","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":"Q925035$705725D2-7A44-4DFD-9A90-76E05D781B90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5da08025eb9e3947f99fa32f0f68740ab3b7eb74","datavalue":{"value":{"entity-type":"item","numeric-id":3475296,"id":"Q3475296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd6c365777d66b54123ee2e9fc3e452440aa16db","datavalue":{"value":{"amount":"+0.7287452816963196","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":"Q925035$27F58ACE-B091-4B75-8BC0-191707FE2CC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bea083e1623c6649a814510eead5e2f43735995d","datavalue":{"value":{"entity-type":"item","numeric-id":3971999,"id":"Q3971999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9900f5a9eb229094cd5e235fbd81224e1303a10c","datavalue":{"value":{"amount":"+0.7047779560089111","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":"Q925035$824F916A-704A-4EF7-A0FD-D61DC52679C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11cdb42faebfbb350f8908ec13e5c2a1470fc781","datavalue":{"value":{"entity-type":"item","numeric-id":4229261,"id":"Q4229261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9900f5a9eb229094cd5e235fbd81224e1303a10c","datavalue":{"value":{"amount":"+0.7047779560089111","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":"Q925035$44293C2A-6291-4E93-AFB9-E9225C472BFE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:925035","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:925035"}}}}}