Maximum edge colouring problem on graphs that exclude a fixed minor

DOI10.1007/978-3-031-43380-1_21MaRDI QIDQ6442704zbMATH OpenOpenAlexFDO

Authors Zdeněk Dvořák, Abhiruk Lahiri

Publication date 5 July 2023

Full work available at URL https://doi.org/10.1007/978-3-031-43380-1_21

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

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.

Cited in

(2)

• Approximating maximum edge 2-coloring by normalizing graphs
• Parameterized algorithms and hardness for the maximum edge q-coloring problem

This page was built for publication: Maximum edge colouring problem on graphs that exclude a fixed minor

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6442704)