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

Mixed hypergraphs and other coloring problems, 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