A linear time algorithm for 7-[3]coloring triangle-free hexagonal graphs

DOI10.1016/J.IPL.2012.02.008MaRDI QIDQ436606zbMATH OpenOpenAlexFDO

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

Publication date 25 July 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2012.02.008

zbMATH Keywords

approximation algorithmgraph algorithmfrequency planninghexagonal graphmulticoloring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Communication networks in operations research (90B18)

Recommendations

• Simpler multicoloring of triangle-free hexagonal graphs
• \(1\)-local \(7/5\)-competitive algorithm for multicoloring hexagonal graphs
• A technique for multicoloring triangle-free hexagonal graphs
• 2-local 7/6-competitive algorithm for multicolouring a sub-class of hexagonal graphs
• A distributed \(6/5\)-competitive algorithm for multicoloring triangle-free hexagonal graphs

Cites work

• 2-local 5/4-competitive algorithm for multicoloring triangle-free hexagonal graphs
• 2-local 7/6-competitive algorithm for multicolouring a sub-class 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 technique for multicoloring triangle-free hexagonal graphs
• Channel assignment and multicolouring of the induced subgraphs of the triangular lattice
• Channel assignment and weighted coloring
• Distributed Online Frequency Assignment in Cellular Networks
• Finding a five bicolouring of a triangle-free subgraph of the triangular lattice
• Simpler multicoloring of triangle-free hexagonal graphs
• Static frequency assignment in cellular networks

Cited in

(3)

• Simpler multicoloring of triangle-free hexagonal graphs
• A technique for multicoloring triangle-free hexagonal graphs
• Solving 7 7 hex with domination, fill-in, and virtual connections

This page was built for publication: A linear time algorithm for \(7\)-\([3]\)coloring triangle-free hexagonal graphs

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