Multicoloring of cannonball graphs

DOI10.26493/1855-3974.528.751MaRDI QIDQ2810379zbMATH OpenOpenAlexWikidataFDO

Authors Rafał Witkowski, Janez Žerovnik, Petra Šparl

Publication date 1 June 2016

Published in Ars Mathematica Contemporanea (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.2688

zbMATH Keywords

approximation algorithmcellular networksfrequency planninggraph coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Abstract: The frequency allocation problem that appeared in the design of cellular telephone networks can be regarded as a multicoloring problem on a weighted hexagonal graph, which opened some still interesting mathematical problems. We generalize the multicoloring problem into higher dimension and present the first jz{approximation} algorithms for multicoloring of so called cannonball graphs.

Recommendations

• A 1-local 4/3-competitive algorithm for multicoloring a subclass of hexagonal graphs
• 2-local <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mn>4</mml:mn><mml:mo stretchy="false">/</mml:mo><mml:mn>3</mml:mn></mml:math>-competitive algorithm for multicoloring hexagonal graphs
• A 1-Local 13/9-Competitive Algorithm for Multicoloring Hexagonal Graphs
• 1-Local 33/24-Competitive Algorithm for Multicoloring Hexagonal Graphs
• 1-Local 17/12-Competitive Algorithm for Multicoloring Hexagonal Graphs

Cited in

(3)

• Coloring of the \(d^{\text{th}}\) power of the face-centered cubic grid
• New reducible configurations for graph multicoloring with application to the experimental resolution of McDiarmid-Reed's conjecture
• Maximum induced matching of hexagonal graphs

This page was built for publication: Multicoloring of cannonball graphs

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