On the span in channel assignment problems: Bounds, computing and counting

DOI10.1016/S0012-365X(02)00821-XzbMath1014.05024MaRDI QIDQ1810659

Colin J. H. McDiarmid

Publication date: 9 June 2003

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

zbMATH Keywords

chromatic numberchannel assignment problemspanconstraint matrix modelGallai-Roy theoremgraph colourig

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (14)

Assigning channels via the meet-in-the-middle approach ⋮ Some new bounds on \(T_{r}\)-choosability ⋮ Mixed hypergraphs and other coloring problems ⋮ THE GRAPH-BIN PACKING PROBLEM ⋮ Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs ⋮ Channel assignment via fast zeta transform ⋮ Labeling planar graphs with a condition at distance two ⋮ On the \(L(p,1)\)-labelling of graphs ⋮ On \(L(2,1)\)-coloring split, chordal bipartite, and weakly chordal graphs ⋮ Distance constrained labelings of planar graphs with no short cycles ⋮ Graph labellings with variable weights, a survey ⋮ An exact algorithm for the channel assignment problem ⋮ On λ-coloring split, chordal bipartite and weakly chordal graphs ⋮ Distance constrained labelings of \(K_{4}\)-minor free graphs

Cites Work

• Unnamed Item
• A note on the complexity of the chromatic number problem
• Bounds for the frequency assignment problem
• Frequency-distance constraints with large distances
• Arrangements, channel assignments, and associated polynomials
• Channel Assignment on Nearly Bipartite and Bounded Treewidth Graphs
• Determining the Chromatic Number of a Graph
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results

This page was built for publication: On the span in channel assignment problems: Bounds, computing and counting