✦ LIBER ✦

Small Universal Graphs for Bounded-Degree Planar Graphs

✍ Scribed by Michael Capalbo

Publisher: Springer-Verlag
Year: 2002
Tongue: English
Weight: 265 KB
Volume: 22
Category: Article
ISSN: 0209-9683
DOI: 10.1007/s004930200017

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Induced-Universal Graphs for Graphs with

Induced-Universal Graphs for Graphs with Bounded Maximum Degree

✍ Steve Butler 📂 Article 📅 2009 🏛 Springer Japan 🌐 English ⚖ 213 KB

Bounded-Degree Independent Sets in Plana

Bounded-Degree Independent Sets in Planar Graphs

✍ Therese Biedl; Dana F. Wilkinson 📂 Article 📅 2005 🏛 Springer 🌐 English ⚖ 425 KB

On universal graphs for planar oriented

On universal graphs for planar oriented graphs of a given girth

✍ O.V. Borodin; A.V. Kostochka; J. Nešetřil; A. Raspaud; E. Sopena 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 662 KB

The oriented chromatic number o(H) of an oriented graph H is defined to be the minimum order of an oriented graph H' such that H has a homomorphism to H'. If each graph in a class ~ has a homomorphism to the same H', then H' is ~-universal. Let ~k denote the class of orientations of planar graphs wi

Judicious partitions of bounded-degree g

Judicious partitions of bounded-degree graphs

✍ B. Bollobás; A. D. Scott 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB 👁 1 views

## Abstract We prove results on partitioning graphs __G__ with bounded maximum degree. In particular, we provide optimal bounds for bipartitions __V__(__G__) = __V__~1~ ∪ __V__~2~ in which we minimize {__e__(__V__~1~), __e__(__V__~2~)}. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 131–143, 200

Packing triangles in bounded degree grap

Packing triangles in bounded degree graphs

✍ Alberto Caprara; Romeo Rizzi 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 103 KB

We consider the two problems of finding the maximum number of node disjoint triangles and edge disjoint triangles in an undirected graph. We show that the first (respectively second) problem is polynomially solvable if the maximum degree of the input graph is at most 3 (respectively 4), whereas it i

Homomorphism bounds for oriented planar

Homomorphism bounds for oriented planar graphs

✍ T. H. Marshall 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB

## Abstract If ${\cal C}$ is a class of oriented graphs (directed graphs without opposite arcs), then an oriented graph is a __homomorphism bound__ for ${\cal C}$ if there is a homomorphism from each graph in ${\cal C}$ to __H__. We find some necessary conditions for a graph to be a homomorphism bo