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 number; channel assignment problem; span; constraint matrix model; Gallai-Roy theorem; graph colourig

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

Related Items

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

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