✦ LIBER ✦

Channel Assignment on Nearly Bipartite and Bounded Treewidth Graphs

✍ Scribed by Colin McDiarmid; Bruce Reed

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 190 KB
Volume: 10
Category: Article
ISSN: 1571-0653
DOI: 10.1016/s1571-0653(04)00393-2

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Channel assignment on graphs of bounded

Channel assignment on graphs of bounded treewidth

✍ Colin McDiarmid; Bruce Reed 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 211 KB

On bounded treewidth duality of graphs

✍ Ne?et?il, Jaroslav; Zhu, Xuding 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 734 KB

For a graph H , the H-coloring problem is to decide whether or not an instance graph G is homomorphic to H . The H-coloring problem is said to have bounded treewidth duality if there is an integer k such that for any graph G which is not homomorphic to H , there is a graph F of treewidth k which is

Channel assignment on Cayley graphs

✍ Patrick Bahls 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB

We address various channel assignment problems on the Cayley graphs of certain groups, computing the frequency spans by applying group theoretic techniques. In particular, we show that if G is the Cayley graph of an n-generated group with a certain kind of presentation, then (G; k, 1) ≤ 2(k +n-1). F

On Dense Bipartite Graphs of Girth Eight

On Dense Bipartite Graphs of Girth Eight and Upper Bounds for Certain Configurations in Planar Point–Line Systems

✍ D de Caen; L.A Székely 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 956 KB

In earlier work we showed that if G(m, n) is a bipartite graph with no 4-cycles or 6-cycles, and if m<c 1 n 2 and n<c 2 m 2 , then the number of edges e is O((mn) 2Â3 ). Here we give a more streamlined proof, obtaining some sharp results; for example, if G has minimum degree at least two then e 3 -