Digital repository of Slovenian research organisations

Show document
A+ | A- | Help | SLO | ENG

Title:Injective coloring of graphs revisited
Authors:ID Brešar, Boštjan (Author)
ID Samadi, Babak (Author)
ID Yero, Ismael G. (Author)
Files:.pdf PDF - Presentation file, download (460,72 KB)
MD5: 6E8358E6F504EA4CDB807E1BC77D0BBF
 
URL URL - Source URL, visit https://www.sciencedirect.com/science/article/pii/S0012365X23000341
 
Language:English
Typology:1.01 - Original Scientific Article
Organization:Logo IMFM - Institute of Mathematics, Physics, and Mechanics
Abstract:An 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 $\chi_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 $\chi_i(G) \ge \frac{1}{2}\sqrt{\frac{1}{4}+\frac{2m-n}{\rho^{o}}}$ holds for any connected graph $G$ of order $n\ge 2$, size $m$, and the open packing number ${\rho^{o}}$, and characterize the class of graphs attaining the bound. Regarding the well known bound $\chi_i(G)\ge \Delta(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 $\chi_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.
Keywords:two-step graph of a graph, injective coloring, open packing, hypercubes
Publication status:Published
Publication version:Version of Record
Publication date:01.05.2023
Year of publishing:2023
Number of pages:art. 113348 (12 str.)
Numbering:Vol. 346, iss. 5
PID:20.500.12556/DiRROS-18637 New window
UDC:519.17
ISSN on article:0012-365X
DOI:10.1016/j.disc.2023.113348 New window
COBISS.SI-ID:141111555 New window
Publication date in DiRROS:09.04.2024
Views:522
Downloads:212
Metadata:XML DC-XML DC-RDF
:
Copy citation
  
Share:Bookmark and Share


Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:Discrete mathematics
Shortened title:Discrete math.
Publisher:Elsevier
ISSN:0012-365X
COBISS.SI-ID:1118479 New window

Document is financed by a project

Funder:ARRS - Slovenian Research Agency
Project number:P1-0297
Name:Teorija grafov

Funder:ARRS - Slovenian Research Agency
Project number:J1-2452
Name:Strukturni, optimizacijski in algoritmični problemi v geometrijskih in topoloških predstavitvah grafov

Funder:ARRS - Slovenian Research Agency
Project number:J1-3002
Name:Prirejanja in barvanja povezav v kubičnih grafih

Funder:Other - Other funder or multiple funders
Funding programme:FEDER-UPO Research and Development Call
Project number:UPO-1263769

Funder:Other - Other funder or multiple funders
Funding programme:“José Castillejo” program for young researchers
Project number:CAS21/00100

Licences

License:CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
Link:http://creativecommons.org/licenses/by-nc-nd/4.0/
Description:The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.

Secondary language

Language:Slovenian
Keywords:dvostopenjski graf grafa, injektivno barvanje, odprto pakiranje, hiperkocke


Back