20.500.12556/DiRROS-27409 List strong and list normal edge-coloring of (sub)cubic graphs Seznamsko krepko in seznamsko normalno barvanje povezav subkubičnih grafov A ▫${\ strong edge-coloring}$▫ of a graph is a proper edge-coloring, in which the edges of every path of length ▫$3$▫ receive distinct colors; in other words, every pair of edges at distance at most ▫$2$▫ must be colored differently. The least number of colors needed for a strong edge-coloring of a graph is the ▫${\ strong chromatic index}$▫. We consider the list version of the coloring and prove that the list strong chromatic index of graphs with maximum degree ▫$3$▫ is at most ▫$10$▫. This bound is tight and improves the previous bound of ▫$11$▫ colors. We also consider the question whether the strong chromatic index and the list strong chromatic index always coincide. We answer it in negative by presenting an infinite family of graphs for which the two invariants differ. For the special case of the Petersen graph, we show that its list strong chromatic index equals ▫$7$▫, while its strong chromatic index is ▫$5$▫. Up to our best knowledge, this is the first known edge-coloring for which there are graphs with distinct values of the chromatic index and its list version. In relation to the above, we also initiate the study of the list version of the normal edge-coloring. A ▫${\ normal edge-coloring}$▫ of a cubic graph is a proper edge-coloring, in which every edge is adjacent to edges colored with ▫$4$▫ distinct colors or to edges colored with ▫$2$▫ distinct colors. It is conjectured that ▫$5$▫ colors suffice for a normal edge-coloring of any bridgeless cubic graph and this statement is equivalent to the Petersen Coloring Conjecture. It turns out that similarly to strong edge-coloring, list normal edge-coloring is much more restrictive and consequently for many graphs the list normal chromatic index is greater than the normal chromatic index. In particular, we show that there are cubic graphs with list normal chromatic index at least ▫$9$▫, there are bridgeless cubic graphs with its value at least ▫$8$▫, and there are cyclically ▫$4$▫-edge-connected cubic graphs with value at least ▫$7$▫. ▫${\ Krepko barvanje povezav}$▫ grafa je pravilno barvanje povezav, pri katerem imajo vse povezave vsake poti dolžine ▫$3$▫ različne barve. Z drugimi besedami, vsaki dve povezavi na razdalji največ ▫$2$▫ morata biti obarvani različno. Najmanjše število barv, potrebnih za krepko barvanje povezav grafa, imenujemo ▫${\ krepki kromatični indeks}$▫. Obravnavamo seznamsko različico barvanja in dokažemo, da je seznamski krepki kromatični indeks grafov z največjo stopnjo ▫$3$▫ kvečjemu ▫$10$▫. Ta meja je tesna in izboljša prejšnjo zgornjo mejo ▫$11$▫ barv. Raziskujemo tudi vprašanje, ali se krepki kromatični indeks in seznamski krepki kromatični indeks vedno ujemata. Na to odgovorimo nikalno, saj predstavimo neskončno družino grafov, pri katerih se ti dve invarianti razlikujeta. Za poseben primer Petersenovega grafa pokažemo, da je njegov seznamski krepki kromatični indeks enak ▫$7$▫, medtem ko je njegov krepki kromatični indeks enak ▫$5$▫. Po našem vedenju je to prvo znano barvanje povezav, za katero obstajajo grafi z različnima vrednostima kromatičnega indeksa in njegove seznamske različice. V povezavi z zgornjim se lotimo tudi preučevanja seznamske različice normalnega barvanja povezav. \emph{Normalno barvanje povezav} kubičnega grafa je pravilno barvanje povezav, pri katerem je vsaka povezava sosednja s povezavami, obarvanimi s ▫$4$▫ različnimi barvami, ali pa s povezavami, obarvanimi z ▫$2$▫ različnima barvama. Obstaja domneva, da zadostuje ▫$5$▫ barv za normalno barvanje povezav vsakega kubičnega grafa brez mostov, pri čemer je ta izrek ekvivalenten \emph{Domnevi o Petersenovem barvanju}. Izkazalo se je, da je – podobno kot pri krepkem barvanju povezav – seznamsko normalno barvanje povezav precej bolj omejujoče, in je zato pri številnih grafih seznamski normalni kromatični indeks večji od normalnega kromatičnega indeksa. Natančneje, pokažemo, da obstajajo kubični grafi s seznamskim normalnim kromatičnim indeksom vsaj ▫$9$▫, kubični grafi brez mostov z vrednostjo vsaj ▫$8$▫, ter ciklično ▫$4$▫-povezani kubični grafi z vrednostjo vsaj ▫$7$▫. strong edge-coloring list strong edge-coloring normal edge-coloring list normal edge-coloring Petersen coloring Petersen coloring conjecture krepko barvanje povezav seznamsko krepko barvanje povezav normalno barvanje povezav seznamsko normalno barvanje povezav Petersenovo barvanje Domneva o Petersenovem barvanju true false true Angleški jezik Slovenski jezik © 2025 The Author(s) Neznano 2026-02-05 15:53:15 2026-02-05 15:53:16 2026-02-06 03:51:22 0000-00-00 00:00:00 2026 0 0 Nasl. z nasl. zaslona; Opis vira z dne 19. 9. 2025; Soavtorji: Edita Máčajová, Roman Soták, Diana Švecová; str. 1-19 Vol. 131 Jan. 2026 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2026-01-01 519.17 1095-9971 10.1016/j.ejc.2025.104243 249652995 RAZ_Luzar_Borut_2026.pdf RAZ_Luzar_Borut_2026.pdf 1 77221426629BB0AE092A3F5B241ACC01 ff7c198ca6406e4f4b4a5e66862fde2e5b2009d993fbae80e8152444cb892f8f 7f9c8822-02a2-11f1-93b0-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=40096 Rudolfovo – Znanstveno in tehnološko središče Novo mesto 0 0 0