✦ LIBER ✦

The number of shortest cycles and the chromatic uniqueness of a graph

✍ Scribed by C. P. Teo; K. M. Koh

Publisher: John Wiley and Sons
Year: 1992
Tongue: English
Weight: 403 KB
Volume: 16
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190160103

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

For a graph G, let g(G) and σ~g~(G) denote, respectively, the girth of G and the number of cycles of length g(G) in G. In this paper, we first obtain an upper bound for σ~g~(G) and determine the structure of a 2‐connected graph G when σ~g~(G) attains the bound. These extremal graphs are then more‐or‐less classified, but one case leads to an unsolved problem. The structural results are finally applied to show that certain families of graphs are chromatically unique.

📜 SIMILAR VOLUMES

The star chromatic number of a graph

✍ H. L. Abbott; B. Zhou 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 469 KB

## Abstract We study a generalization of the notion of the chromatic number of a graph in which the colors assigned to adjacent vertices are required to be, in a certain sense, far apart. © 1993 John Wiley & Sons, Inc.

The chromatic covering number of a graph

✍ Reza Naserasr; Claude Tardif 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 72 KB 👁 1 views

Following [1] , we investigate the problem of covering a graph G with induced subgraphs G 1 ; . . . ; G k of possibly smaller chromatic number, but such that for every vertex u of G, the sum of reciprocals of the chromatic numbers of the G i 's containing u is at least 1. The existence of such ''ch

Rank and chromatic number of a graph

✍ Kotlov, Andrei? 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB 👁 2 views

It was proved (A. Kotlov and L. Lovász, The rank and size of graphs, J. Graph Theory 23 (1996), 185-189) that the number of vertices in a twin-free graph is O(( √ 2) r ) where r is the rank of the adjacency matrix. This bound was shown to be tight. We show that the chromatic number of a graph is o(∆

The chromatic number of oriented graphs

✍ Sopena, Eric 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB 👁 2 views

We introduce in this paper the notion of the chromatic number of an oriented graph G (that is of an antisymmetric directed graph) defined as the minimum order of an oriented graph H such that G admits a homomorphism to H. We study the chromatic number of oriented k-trees and of oriented graphs with

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 👁 1 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 👁 1 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_