Charles Explorer logo
🇬🇧

Maximum Edge Colouring Problem On Graphs That Exclude a Fixed Minor

Publication at Faculty of Mathematics and Physics |
2023

Abstract

The maximum edge colouring problem considers the maximum colour assignment to edges of a graph under the condition that every vertex has at most a fixed number of distinct coloured edges incident on it. If that fixed number is q we call the colouring a maximum edge q-colouring.

The problem models a non-overlapping frequency channel assignment question on wireless networks. The problem has also been studied from a purely combinatorial perspective in the graph theory literature.

We study the question when the input graph is sparse. We show the problem remains NP-hard on 1-apex graphs.

We also show that there exists PTAS for the problem on minor-free graphs. The PTAS is based on a recently developed Baker game technique for proper minor-closed classes, thus avoiding the need to use any involved structural results.

This further pushes the Baker game technique beyond the problems expressible in the first-order logic.