Finding a five bicolouring of a triangle-free subgraph of the triangular lattice

DOI10.1016/S0012-365X(01)00079-6zbMath0997.05033MaRDI QIDQ1349081

Frédéric Havet, Janez Žerovnik

Publication date: 21 May 2002

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

triangular latticehexagonal cellsdistributed algorithmweighted colouring

Mathematics Subject Classification ID

Applications of graph theory (05C90) Coloring of graphs and hypergraphs (05C15)

Related Items

Every triangle-free induced subgraph of the triangular lattice is \((5m,2m)\)-choosable ⋮ 2-local 5/4-competitive algorithm for multicoloring triangle-free hexagonal graphs ⋮ 1-local 7/5-competitive algorithm for multicoloring hexagonal graphs ⋮ A linear time algorithm for \(7\)-\([3\)coloring triangle-free hexagonal graphs] ⋮ Simpler multicoloring of triangle-free hexagonal graphs ⋮ 2-local 7/6-competitive algorithm for multicolouring a sub-class of hexagonal graphs ⋮ IMPROPER COLORING OF WEIGHTED GRID AND HEXAGONAL GRAPHS ⋮ Homomorphisms of hexagonal graphs to odd cycles ⋮ A technique for multicoloring triangle-free hexagonal graphs ⋮ 2-local distributed algorithms for generalized coloring of hexagonal graphs