Maximum Edge Colouring Problem On Graphs That Exclude a Fixed Minor

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10473814" target="_blank" >RIV/00216208:11320/23:10473814 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1007/978-3-031-43380-1_21" target="_blank" >https://doi.org/10.1007/978-3-031-43380-1_21</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-43380-1_21" target="_blank" >10.1007/978-3-031-43380-1_21</a>

Result language

angličtina

Original language name

Maximum Edge Colouring Problem On Graphs That Exclude a Fixed Minor

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA22-17398S" target="_blank" >GA22-17398S: Flows and cycles in graphs on surfaces</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2023

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ISBN

978-3-031-43379-5

ISSN

—

e-ISSN

1611-3349

Number of pages

14

Pages from-to

291-304

Publisher name

Springer

Place of publication

Switzerland

Event location

Fribourg, Switzerland

Event date

Jun 28, 2023

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—