Show simple item record

dc.contributor.authorBrešar, Boštjan
dc.contributor.authorSamadi, Babak
dc.contributor.authorGonzález Yero, Ismael 
dc.contributor.otherMatemáticases_ES
dc.date.accessioned2023-10-17T09:03:04Z
dc.date.available2023-10-17T09:03:04Z
dc.date.issued2023-02-02
dc.identifier.issn0012-365X
dc.identifier.urihttp://hdl.handle.net/10498/29437
dc.description.abstractAn open packing in a graph G is a set S of vertices in G such that no two vertices in S have a common neighbor in G. The injective chromatic number χi(G) of G is the smallest number of colors assigned to vertices of G such that each color class is an open packing. Alternatively, the injective chromatic number of G is the chromatic number of the two-step graph of G, which is the graph with the same vertex set as G in which two vertices are adjacent if they have a common neighbor. The concept of injective coloring has been studied by many authors, while in the present paper we approach it from two novel perspectives, related to open packings and the two-step graph operation. We prove several general bounds on the injective chromatic number expressed in terms of the open packing number. In particular, we prove that χi(G)≥[Formula presented] holds for any connected graph G of order n≥2, size m, and the open packing number ρo, and characterize the class of graphs attaining the bound. Regarding the well known bound χi(G)≥Δ(G), we describe the family of extremal graphs and prove that deciding when the equality holds (even for regular graphs) is NP-complete, solving an open problem from an earlier paper. Next, we consider the chromatic number of the two-step graph of a graph, and compare it with the clique number and the maximum degree of the graph. We present two large families of graphs in which χi(G) equals the cardinality of a largest clique of the two-step graph of G. Finally, we consider classes of graphs that admit an injective coloring in which all color classes are maximal open packings. We give characterizations of three subclasses of these graphs among graphs with diameter 2, and find a partial characterization of hypercubes with this property.es_ES
dc.formatapplication/pdfes_ES
dc.language.isoenges_ES
dc.publisherElsevieres_ES
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 Internacional*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.sourceDiscrete Mathematics. Vol. 346, nº 5, May 2023, 113348es_ES
dc.subjectHypercubees_ES
dc.subjectInjective coloringes_ES
dc.subjectOpen packinges_ES
dc.subjectTwo-step graph of a graphes_ES
dc.titleInjective coloring of graphs revisitedes_ES
dc.typejournal articlees_ES
dc.rights.accessRightsopen accesses_ES
dc.description.physDesc12 páginases_ES
dc.identifier.doi10.1016/j.disc.2023.113348
dc.relation.projectIDP1-0297es_ES
dc.relation.projectIDJ1-2452es_ES
dc.relation.projectIDJ1-3002es_ES
dc.relation.projectIDUPO-1263769es_ES
dc.relation.projectIDCAS21/00100es_ES
dc.type.hasVersionVoRes_ES


Files in this item

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivatives 4.0 Internacional
This work is under a Creative Commons License Attribution-NonCommercial-NoDerivatives 4.0 Internacional