𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On universal graphs for planar oriented graphs of a given girth

✍ Scribed by O.V. Borodin; A.V. Kostochka; J. Nešetřil; A. Raspaud; E. Sopena

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
662 KB
Volume
188
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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 with girth at least k. Clearly, ~3 ~ ~4 ~ ~5... We discuss the existence of ~k-universal graphs with special properties. It is known (see that there exists a ~3-universal graph on 80 vertices. We prove here that (1) there exist no planar ~4-universal graphs;

(2) there exists a planar ~16-universal graph on 6 vertices;

(3) for any k, there exist no planar ~k-universal graphs of girth at least 6;

(4) for any k, there exists a ~40k-universal graph of girth at least k + 1.

📜 SIMILAR VOLUMES

The Laplacian spectral radius of bicycli
The Laplacian spectral radius of bicyclic graphs with a given girth
✍ Mingqing Zhai; Guanglong Yu; Jinlong Shu 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 622 KB

Let B(n, g) be the class of bicyclic graphs on n vertices with girth g. Let B 1 (n, g) be the subclass of B(n, g) consisting of all bicyclic graphs with two edge-disjoint cycles and B 2 (n, g) = B(n, g) \ B 1 (n, g). This paper determines the unique graph with the maximal Laplacian spectral radius a

A lower bound on the order of regular gr
A lower bound on the order of regular graphs with given girth pair
✍ C. Balbuena; T. Jiang; Y. Lin; X. Marcote; M. Miller 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB 👁 1 views

## Abstract The girth pair of a graph gives the length of a shortest odd and a shortest even cycle. The existence of regular graphs with given degree and girth pair was proved by Harary and Kovács [Regular graphs with given girth pair, J Graph Theory 7 (1983), 209–218]. A (δ, __g__)‐cage is a small

A class of planar well-covered graphs wi
A class of planar well-covered graphs with girth four
✍ Michael R. Pinter 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 616 KB

## Abstract A well‐covered graph is a graph in which every maximal independent set is a maximum independent set; Plummer introduced the concept in a 1970 paper. The notion of a 1‐well‐covered graph was introduced by Staples in her 1975 dissertation: a well‐covered graph __G__ is 1‐well‐covered if a