1-local 7/5-competitive algorithm for multicoloring hexagonal graphs

DOI10.1016/J.ENDM.2010.05.048MaRDI QIDQ2883583zbMATH OpenOpenAlexFDO

Authors Rafał Witkowski, Janez Žerovnik

Publication date 13 May 2012

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2010.05.048

zbMATH Keywords

frequency assignmenthexagonal graphmulticoloring

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)

Recommendations

• 1-local 7/5-competitive algorithm for multicoloring hexagonal graphs
• 1-Local 17/12-Competitive Algorithm for Multicoloring Hexagonal Graphs
• 2-local 7/6-competitive algorithm for multicolouring a sub-class of hexagonal graphs
• 2-local 5/4-competitive algorithm for multicoloring triangle-free hexagonal graphs
• 1-Local 33/24-Competitive Algorithm for Multicoloring Hexagonal Graphs
• 1-local 33/24-competitive algorithm for multicoloring hexagonal graphs
• A 1-local 4/3-competitive algorithm for multicoloring a subclass of hexagonal graphs
• A 1-Local 13/9-Competitive Algorithm for Multicoloring 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 asymptotic 13/9-competitive algorithm for multicoloring hexagonal graphs

Cites work

• 1-Local 17/12-Competitive Algorithm for Multicoloring 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 asymptotic 13/9-competitive algorithm for multicoloring hexagonal graphs
• A technique for multicoloring triangle-free hexagonal graphs
• Channel assignment and weighted coloring
• Distributed Online Frequency Assignment in Cellular Networks
• Static frequency assignment in cellular networks

Cited in

(4)

• A linear time algorithm for \(7\)-\([3]\)coloring triangle-free hexagonal graphs
• 1-Local 33/24-Competitive Algorithm for Multicoloring Hexagonal Graphs
• Simpler multicoloring of triangle-free hexagonal graphs
• A 1-Local 13/9-Competitive Algorithm for Multicoloring Hexagonal Graphs

This page was built for publication: \(1\)-local \(7/5\)-competitive algorithm for multicoloring hexagonal graphs

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