✦ LIBER ✦

Homomorphism bounds for oriented planar graphs

✍ Scribed by T. H. Marshall

Publisher: John Wiley and Sons
Year: 2007
Tongue: English
Weight: 202 KB
Volume: 55
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20233

No coin nor oath required. For personal study only.

✦ Synopsis

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 bound for the class of oriented planar graphs and prove that such a graph must have maximum degree at least 16; thus there exists an oriented planar graph with oriented chromatic number at least 17. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 175–190, 2007

📜 SIMILAR VOLUMES

Extremal graphs for homomorphisms

✍ Jonathan Cutler; A. J. Radcliffe 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB

The study of graph homomorphisms has a long and distinguished history, with applications in many areas of graph theory. There has been recent interest in counting homomorphisms, and in particular on the question of finding upper bounds for the number of homomorphisms from a graph G into a fixed imag

New upper bounds on the decomposability

New upper bounds on the decomposability of planar graphs

✍ Fedor V. Fomin; Dimitrios M. Thilikos 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 335 KB 👁 1 views

## Abstract It is known that a planar graph on __n__ vertices has branch‐width/tree‐width bounded by $\alpha \sqrt {n}$. In many algorithmic applications, it is useful to have a small bound on the constant α. We give a proof of the best, so far, upper bound for the constant α. In particular, for th

Combinatorial curvature for planar graph

Combinatorial curvature for planar graphs

✍ Yusuke Higuchi 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 113 KB

## Abstract Regarding an infinite planar graph __G__ as a discrete analogue of a noncompact simply connected Riemannian surface, we introduce the combinatorial curvature of __G__ corresponding to the sectional curvature of a manifold. We show this curvature has the property that its negative values

A GRASP for graph planarization

✍ Resende, Mauricio G. C.; Ribeiro, Celso C. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 268 KB 👁 2 views

A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. In this paper, we describe a GRASP for the graph planarization problem, extending the heuristic of Goldschmidt and Takvorian [ Networks 24 (1994) 69-73]. We review the basic concepts of GRASP: co

An algorithm for drawing planar graphs

✍ Bor Plestenjak 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 382 KB 👁 2 views

A simple algorithm for drawing 3-connected planar graphs is presented. It is derived from the Fruchterman and Reingold spring embedding algorithm by deleting all repulsive forces and fixing vertices of an outer face. The algorithm is implemented in the system for manipulating discrete mathematical s

New bounds for the chromatic number of g

New bounds for the chromatic number of graphs

✍ Manouchehr Zaker 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB 👁 1 views

## Abstract In this article we first give an upper bound for the chromatic number of a graph in terms of its degrees. This bound generalizes and modifies the bound given in 11. Next, we obtain an upper bound of the order of magnitude ${\cal O}({n}^{{1}-\epsilon})$ for the coloring number of a graph