Injective colorings of Sierpiński-like graphs and Kneser graphs

Brešar, Boštjan (avtor), Klavžar, Sandi (avtor), Samadi, Babak (avtor), Yero, Ismael G. (avtor)

Two relationships between the injective chromatic number and, respectively, chromatic number and chromatic index, are proved. They are applied to determine the injective chromatic number of Sierpiński graphs and to give a short proof that Sierpiński graphs are Class 1. Sierpiński-like graphs are also considered, including generalized Sierpiński graphs over cycles and rooted products. It is proved that the injective chromatic number of a rooted product of two graphs lies in a set of six possible values. Sierpiński graphs and Kneser graphs $K(n,r)$ are considered with respect of being perfect injectively colorable, where a graph is perfect injectively colorable if it has an injective coloring in which every color class forms an open packing of largest cardinality. In particular, all Sierpiński graphs and Kneser graphs $K(n,r)$ with $n\ge 3r-1$, are perfect injectively colorable, while $K(7,3)$ is not.

• Jezik: Angleški jezik
• Ključne besede: injective coloring, injective chromatic number, perfect injectively colorable graph, Sierpiński graphs, Kneser graphs, rooted product graph
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Datum objave: 01.08.2025
• Leto izida: 2025
• Št. strani: 22 str.
• Številčenje: Vol. 41, iss. 4, art. no. 83
• PID: 20.500.12556/RUL-170988
• UDK: 519.17
• ISSN pri članku: 0911-0119
• DOI: 10.1007/s00373-025-02952-3
• COBISS.SI-ID: 243802627
• Datum objave v RUL: 25.07.2025

Gradivo je del revije

• Naslov: Graphs and combinatorics
• Skrajšan naslov: Graphs comb.
• Založnik: Springer
• ISSN: 0911-0119
• COBISS.SI-ID: 25536512

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: injektivno barvanje, injektivno kromatično število, popolno injektivno obarljiv graf, grafi Sierpińskega, Kneserjevi grafi, korenski produkt grafov