20.500.12556/RUP-21526 On balanceable and simply balanceable regular graphs We continue the study of balanceable graphs, defined by Caro, Hansberg, and Montejano in 2021 as graphs G such that any 2-coloring of the edges of a sufficiently large complete graph containing sufficiently many edges of each color contains a balanced copy of G (that is, a copy with half the edges of each color). While the problem of recognizing balanceable graphs was conjectured to be NP-complete by Dailly, Hansberg, and Ventura in 2021, balanceable graphs admit an elegant combinatorial characterization: a graph is balanceable if and only there exist two vertex subsets, one containing half of all the graph’s edges and another one such that the corresponding cut contains half of all the graph’s edges. We consider a special case of this property, namely when one of the two sets is a vertex cover, and call the corresponding graphs simply balanceable. We prove a number of results on balanceable and simply balanceable regular graphs. First, we characterize simply balanceable regular graphs via a condition involving the independence number of the graph. Second, we address a question of Dailly, Hansberg, and Ventura from 2021 and show that every cubic graph is balanceable. Third, using Brooks’ theorem, we show that every 4-regular graph with order divisible by 4 is balanceable. Finally, we show that it is NP-complete to determine if a 9-regular graph is simply balanceable. balanceable graph simply balanceable graph cubic graph 4-regular graph regular graph independent set uravnotežen graf enostavno uravnotežen graf kubičen graf 4-regularen graf regularen graf neodvisna množica true false false Angleški jezik Slovenski jezik Članek v reviji 2025-08-06 10:06:01 2025-08-06 10:06:02 2025-08-07 03:04:45 0000-00-00 00:00:00 2025 0 0 str. 1-14 [article no.] ǂ104045 Vol. 124 Feb. 2025 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 2024-08-24 519.17 0195-6698 10.1016/j.ejc.2024.104045 207809283 RAZ_Ahanjideh_Milad_2025.pdf RAZ_Ahanjideh_Milad_2025.pdf 1 17134BC39DD01C6322A17CC89008D45E 0d98fddbf3432396b63a746abcdead1253f8811d2836506ccd843921d12a572d 600d2507-729c-11f0-8f0b-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=31301 https://doi.org/10.1016/j.ejc.2024.104045 1 36709438-729c-11f0-8f0b-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=31300 Fakulteta za matematiko, naravoslovje in informacijske tehnologije 0 0 0