20.500.12556/DKUM-65349 On acyclic colorings of direct products Aciklična barvanja direktnih produktov A coloring of a graph ▫$G$▫ is an acyclic coloring if the union of any two color classes induces a forest. It is proved that the acyclic chromatic number of direct product of two trees ▫$T_1$▫ and ▫$T_2$▫ equals ▫$\min\{ \Delta(T_1) + 1, \Delta(T_2) + 1\}$▫. We also prove that the acyclic chromatic number of direct product of two complete graphs ▫$K_m$▫ and ▫$K_n$▫ is ▫$mn-m-2$▫, where ▫$m \ge n \ge 4$▫. Several bounds for the acyclic chromatic number of direct products are given and in connection to this some questions are raised. Barvanje grafa je aciklično, če je poljubna unija dveh barvnih razredov gozd. Dokazano je, da je aciklično kromatično število produkta dveh dreves ▫$T_1$▫ in ▫$T_2$▫ enako ▫$\min\{ \Delta(T_1)+1, \Delta(T_2)+1\}$▫. Prav tako je dokazano, da je aciklično kromatično število dveh polnih grafov ▫$K_m$▫ in ▫$K_n$▫ enako ▫$mn-m-2$▫, kjer je ▫$m \ge n \ge 4$▫. Številne meje za aciklično kromatično število so podane in v zvezi s tem so zastavljena nekatera vprašanja. mathematics graph theory coloring acyclic coloring distance-two coloring direct product matematika teorija grafov barvanje aciklično barvanje barvanje s pogojem na razdalji dva direktni produkt grafov true false true Angleški jezik Slovenski jezik Znanstveno delo 2017-03-31 14:13:19 2017-03-31 14:14:19 2022-07-08 03:07:40 2019-07-11 15:15:25 2008 0 0 str. 323-333 št. 2 Letn. 28 2008 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1234-3099 519.17 7487065 14893401 1234-3099 URN:SI:UM:DK:8LGTYPFJ Discussiones_Mathematicae_Graph_Theory_2008_Spacapan,_Tepeh_On_acyclic_colorings_of_direct_products.pdf Discussiones_Mathematicae_Graph_Theory_2008_Spacapan,_Tepeh_On_acyclic_colorings_of_direct_products.pdf 1 D9B4EBB189ABF137C6F5A73BF3A66322 d57e06f9222123cbee9183830ac11bd551ee4c8e730f12930b7602a18ef2f6df 0bcce47a-7c0e-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=110425 http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.1363 1 https://dk.um.si/Dokument.php?lang=slv&id=110424 Fakulteta za strojništvo 0 0 0