✦ LIBER ✦

A better bound for the cop number of general graphs

✍ Scribed by Ehsan Chiniforooshan

Publisher: John Wiley and Sons
Year: 2008
Tongue: English
Weight: 85 KB
Volume: 58
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20291

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this note, we prove that the cop number of any n‐vertex graph G, denoted by ${{c}}({{G}})$, is at most ${{O}}\big({{{n}}\over {{\rm lg}} {{n}}}\big)$. Meyniel conjectured ${{c}}({{G}})={{O}}(\sqrt{{{n}}})$. It appears that the best previously known sublinear upper‐bound is due to Frankl, who proved ${{c}}({{G}})\leq ({{1}}+ {{o}}({{1}})){{{n}}{{\rm lg}}{{\rm lg}} {{n}}\over {{\rm lg}} {{n}}}$. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 45–48, 2008

📜 SIMILAR VOLUMES

A general upper bound for the cyclic chr

A general upper bound for the cyclic chromatic number of 3-connected plane graphs

✍ Hikoe Enomoto; Mirko Horňák 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 457 KB 👁 1 views

## Abstract The cyclic chromatic number of a plane graph __G__ is the smallest number χ~__c__~(__G__) of colors that can be assigned to vertices of __G__ in such a way that whenever two distinct vertices are incident with a common face, they receive distinct colors. It was conjectured by Plummer an

Bounds for the harmonious chromatic numb

Bounds for the harmonious chromatic number of a graph

✍ I. Krasikov; Y. Roditty 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 231 KB 👁 2 views

## Abstract The upper bound for the harmonious chromatic number of a graph given by Zhikang Lu and by C. McDiarmid and Luo Xinhua, independently (__Journal of Graph Theory__, 1991, pp. 345–347 and 629–636) and the lower bound given by D. G. Beane, N. L. Biggs, and B. J. Wilson (__Journal of Graph T

Improved bounds for the chromatic number

Improved bounds for the chromatic number of a graph

✍ S. Louis Hakimi; Edward Schmeichel 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB 👁 2 views

## Abstract After giving a new proof of a well‐known theorem of Dirac on critical graphs, we discuss the elegant upper bounds of Matula and Szekeres‐Wilf which follow from it. In order to improve these bounds, we consider the following fundamental coloring problem: given an edge‐cut (__V__~1~, __V_

Bounds for the ramsey number of a discon

Bounds for the ramsey number of a disconnected graph versus any graph

✍ Ronald J. Gould; Michael S. Jacobson 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 200 KB 👁 1 views

## Abstract Bounds are determined for the Ramsey number of the union of graphs versus a fixed graph __H__, based on the Ramsey number of the components versus __H__. For certain unions of graphs, the exact Ramsey number is determined. From these formulas, some new Ramsey numbers are indicated. In p

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

New upper bounds for the chromatic numbe

New upper bounds for the chromatic number of a graph

✍ Ladislav Stacho 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 55 KB 👁 3 views