2023/11/15 by Čada, Roman, Furuya, Michitaka, Kimura, Kenji +3
#05C70 #68Q17 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.2311.09042
The main result of this paper is an edge-coloured version of Tutte's f-factor theorem. We give a necessary and sufficient condition for an edge-coloured graph Gc to have a properly coloured f-factor. We state and prove our result in terms of an auxiliary graph Gfc which has a 1-factor if and only if Gc has a properly coloured f-factor; this is analogous to the "short proof" of the f-factor theorem given by Tutte in 1954. An alternative statement, analogous to the original f-factor theorem, is also given. We show that our theorem generalises the f-factor theorem; that is, the former implies the latter. We consider other properties of edge-coloured graphs, and show that similar results are unlikely for f-factors with rainbow components and distance-d-coloured f-factors, even when d=2 and the number of colours used is asymptotically minimal.