{"entities":{"Q6145804":{"pageid":13280111,"ns":120,"title":"Item:Q6145804","lastrevid":55544545,"modified":"2026-02-17T18:33:54Z","type":"item","id":"Q6145804","labels":{"en":{"language":"en","value":"Injective chromatic index of sparse graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7785853"}},"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":"Q6145804$91C5F29B-DD30-4B86-A2FB-E1FB8B76DCE7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c506e558172a6c05ea878d035c5099cc8876a090","datavalue":{"value":{"text":"Injective chromatic index of sparse graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6145804$66F84060-8082-493A-A211-0EB08B5129D0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6145804$20B3AB5C-AB98-4FAE-AF6F-8F7F1B66996A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9925a2009f7147e973cfc5994d702255fda96853","datavalue":{"value":{"time":"+2024-01-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6145804$4FA31104-3A05-485F-9412-F9C9BEA54451","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ca87feb9857ba6523cdce722d722919ca5a638aa","datavalue":{"value":"A \\(k\\)-injective-edge coloring of a graph \\(G\\) is an assignment of colors, i.e. integers in \\(\\{1, 2, \\ldots , k\\}\\), to the edges of \\(G\\) such that \\(e_1\\) and \\(e_3\\) receive distinct colors for any three consecutive edges \\(e_1\\), \\(e_2\\), \\(e_3\\) of a path or a 3-cycle. The smallest integer \\(k\\) such that \\(G\\) has an injective-edge coloring is called the injective chromatic index of \\(G\\), denoted by \\(\\chi^\\prime_i(G)\\).  For a graph \\(G\\) and a positive integer \\(k\\), \\textit{D. M. Cardoso} et al. [``Injective edge chromatic index of a graph'', Preprint, \\url{arXiv:1510.02626}] proved that it is NP-hard to check whether \\(\\chi^\\prime_i(G)=k\\).  For a simple graph \\(G\\), that is not a cycle with maximum degree \\(\\Delta\\), \\(\\chi^\\prime_i(G)\\le 2(\\Delta-1)^2\\). \\textit{Z. Miao} et al. [Discrete Appl. Math. 310, 65--74 (2022; Zbl 1482.05118)] proposed the following conjecture:  Let \\(G\\) be a simple graph with maximum degree \\(\\Delta\\). Then \\(\\chi^\\prime_i(G)\\le \\Delta(\\Delta-1)\\).  Miao et al. [loc. cit.] attacked this conjecture using the maximum average degree \\(\\mathrm{mad}(G)\\) of a graph \\(G\\). For a graph \\(G\\), its maximum average degree mad\\((G)\\) is mad\\((G) =\\max_{\\emptyset \\ne H\\subseteq G}\\frac{ 2|E(H)|}{|V(H)|}\\).  Namely, Miao et al. [loc. cit.] analyzed graphs with maximum degree \\(\\Delta=4\\). They showed that for the graphs \\(G\\) with \\(\\Delta (G) = 4\\), \\(\\chi^\\prime_i(G)\\le 9\\) \\((\\text{resp.}, 10, 11, 12)\\) if mad\\( (G) < \\frac{14} 5\\) \\((\\text{resp.}, 3, \\frac{19} 6 ,\\frac{ 36}{ 11} )\\).  Similar results were obtained for the graph with maximum degree 5. \\textit{J. Zhu} [Discrete Appl. Math. 334, 119--126 (2023; Zbl 1512.05150)) proved that \\(\\chi^\\prime_i(G)\\le 8\\) \\((\\text{resp.}, 9, 10, 11, 13, 14)\\) if mad\\((G) <\\frac{7}{3}\\) \\((\\text{resp.}, \\frac{12} 5 ,\\frac{ 5} 2 ,\\frac{ 18} 7 , \\frac{14} 5 , 3)\\) for any graphs \\(G\\) with \\(\\Delta (G) = 5\\).  In this paper, the authors improve the upper bounds on the injective chromatic index of such graphs (graphs with maximum degree 5). They show the following: Let \\(G\\) be a simple and finite graph with \\(\\Delta(G)=5\\). Then \\(\\chi^\\prime_i(G)\\le 10\\) \\((\\text{resp.} 11, 12, 13)\\) if mad\\( (G) <\\frac{ 37}{ 14}\\) \\((\\text{resp.} \\frac{39}{14},\\frac{17}{6}, 3)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q6145804$D8739E1E-A185-4F7B-892E-98B43D4B1C17","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f9032c5b8ef1db0564b29cc6cf43db17b3ddeff3","datavalue":{"value":{"entity-type":"item","numeric-id":338804,"id":"Q338804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6145804$EBAC7E9C-F539-45E3-A289-452E0E7A4C64","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6145804$ED36E0C4-E7F9-4AA1-B1EF-E65234CC0BCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cf979f4acdc6dac710cfd0a80dde6754b28a9043","datavalue":{"value":"05C42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6145804$5446A498-534D-4442-B3AA-FE7FC9AAAE9D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"53e9393a158277db0b51871227176edb35820ed6","datavalue":{"value":"7785853","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6145804$2F77C932-C474-4F4C-9237-C8C36D4BDCB6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"334292f7f1772b7b51e2f600d0171fc059b25d67","datavalue":{"value":"injective-edge coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q6145804$4F74088C-E93A-4701-BCEB-DFA0066CD285","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"abb3f5ef5bfe0d22c9079f4c5062a5ca51d55e34","datavalue":{"value":"maximum average degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q6145804$10F68672-52BB-47C6-B500-A313EC3C7F17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13196c9c8a3f396e97e9426bc7763f437026aa4b","datavalue":{"value":"maximum degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q6145804$230F9731-7382-421E-BAF3-C867F4EA1FED","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":"Q6145804$97DD3868-4151-4F9B-B11A-E28D21B901B1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"87b3147237cb4b2277c0797dbfbf5e3e72e303a9","datavalue":{"value":{"entity-type":"item","numeric-id":4634525,"id":"Q4634525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6145804$F9B076A2-B9D6-46EB-927D-FD686C52EE1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86e679d656e5402dd1a8a25684e65e339dbbfcfa","datavalue":{"value":{"entity-type":"item","numeric-id":4983904,"id":"Q4983904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6145804$4D0AAD9D-9E59-4721-A66C-36C2D325CFBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4e5657f6e6c69b8492155a03380e65c10f5cc80","datavalue":{"value":{"entity-type":"item","numeric-id":5864435,"id":"Q5864435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6145804$E503A29C-D69C-4FBF-A778-C3BB0B187DCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a94925cf41f22be40a374f18e6abc480f90dd69","datavalue":{"value":{"entity-type":"item","numeric-id":2032162,"id":"Q2032162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6145804$D258F9C1-45DA-4E1B-ABA3-54B5EE026FA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebc3903ae66420227fc376a665ca50016d3fcf29","datavalue":{"value":{"entity-type":"item","numeric-id":2033899,"id":"Q2033899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6145804$72A25807-4829-447C-8BF9-CD186B9CF71E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"170e0469a5bfc2419bedaea656f8271a5b732f09","datavalue":{"value":{"entity-type":"item","numeric-id":2676764,"id":"Q2676764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6145804$3C4D9EF6-700D-4AA9-A5F8-C9A0C53A79B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"daf4b9fa91055a4101374ccb0f03e6a687ece141","datavalue":{"value":{"entity-type":"item","numeric-id":2043370,"id":"Q2043370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6145804$BAEB6578-EF68-4859-9740-B9204E069D76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f91ba4b14eb577ef5a3138f1b47422e56ad7b29c","datavalue":{"value":{"entity-type":"item","numeric-id":2074357,"id":"Q2074357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6145804$62E0B597-9B92-4F98-BE73-2E0685DFC105","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdf07de20659ed7a840493228b339eeea87ba0ab","datavalue":{"value":{"entity-type":"item","numeric-id":6157424,"id":"Q6157424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6145804$75E4FA5E-BBF0-47B1-A993-20D28886FB79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20bd4ba48b558e7131af728d6379ebf7d6729cf6","datavalue":{"value":{"entity-type":"item","numeric-id":2111524,"id":"Q2111524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6145804$1126FF1B-6983-42DA-8AAA-42AE5BD32826","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"59148ce2421225917fd45cf9b574e3697f808ebd","datavalue":{"value":"10.1016/J.DAM.2023.11.027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6145804$0A6926E6-D41D-48A1-A248-54A8B5E351A6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"078ee0fe58a68cf6dd9ed1995fe754b5d0d8b8d2","datavalue":{"value":{"entity-type":"item","numeric-id":2111524,"id":"Q2111524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"789c45d1b0d177a8d10f898b919d77fc74338141","datavalue":{"value":{"amount":"+0.944036900997162","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":"Q6145804$752376B6-8A9A-4779-B5F4-84E91FBA3236","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b33621e461a586c0ecfb095f72c8d9c4e2d2166b","datavalue":{"value":{"entity-type":"item","numeric-id":6157424,"id":"Q6157424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c7f9091ae51632adb2484695d78964c72d015045","datavalue":{"value":{"amount":"+0.925505757331848","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":"Q6145804$B1091CC2-A044-490B-8D99-090F2B466988","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c471a661dc37f1b0fdb42ffb906c80a4b0633a5","datavalue":{"value":{"entity-type":"item","numeric-id":6585500,"id":"Q6585500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dfc3ac1995f1300256b41e554bd60f8c5fe4a2a7","datavalue":{"value":{"amount":"+0.91531103849411","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":"Q6145804$0CFCE417-3EC8-4E06-8FD6-266E17DE1A6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"715e2a352d3e36a3e515cff7dc8c3b7a18fa8fb9","datavalue":{"value":{"entity-type":"item","numeric-id":4634525,"id":"Q4634525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21a1934d0796fffb7153ecb727f7ab3f82baa783","datavalue":{"value":{"amount":"+0.8908088803291321","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":"Q6145804$0CB09883-6C44-4192-904B-6E00C56D52E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03b059ea925a77305509b9718d879d32eb9cc8bd","datavalue":{"value":{"entity-type":"item","numeric-id":710598,"id":"Q710598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8fd34618e476e4e86ee9a24c5db7c31d3d5de323","datavalue":{"value":{"amount":"+0.8824586868286133","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":"Q6145804$1A09FCA4-48A8-43AF-AE49-0947F6280E2C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6145804","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6145804"}}}}}