✦ LIBER ✦

Some upper bounds for the product of the domination number and the chromatic number of a graph

✍ Scribed by Jerzy Topp; Lutz Volkmann

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 199 KB
Volume: 118
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90074-4

No coin nor oath required. For personal study only.

✦ Synopsis

Topp, J. and L. Volkmann, Some upper bounds for the product of the domination number and the chromatic number of a graph, Discrete Mathematics 118 (1993) 2899292.

Some new upper bounds for yx are proved, where y is the domination number and x is the chromatic number of a graph.

All graphs considered in this note are finite, undirected, and without loops or multiple edges. Our terminology is based on [2]. For a graph G, let n, 6, A,y, and x denote the order, the minimum degree, the maximum degree, the domination number, and the chromatic number of G, respectively.

Recently Gernert [S] has obtained the following two inequalities for the product yx of the domination number and the chromatic number of a graph.

Theorem A. If G is a connected graph with n > 5, then yx <a n2.

Theorem B. If G is a regular graph with n 3 5, then yx <ff n2

, In this note we present some improvements of the above inequalities. The following two lemmas will be useful in our proofs.

📜 SIMILAR VOLUMES

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

Inequalities between the domination numb

Inequalities between the domination number and the chromatic number of a graph

✍ Dieter Gernert 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 230 KB

Upper bounds for u + x and ax are proved, where u is the domination number and x the chromatic number of a graph.

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_

An upper bound for the harmonious chroma

An upper bound for the harmonious chromatic number of a graph

✍ Sin-Min Lee; John Mitchem 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 149 KB 👁 2 views

An upper bound for the harmonious chromatic number of a graph G is given. Three corollaries of the theorem are theorems or improvements of the theorems of Miller and Pritikin. The assignment of colors to the vertices of a graph such that each vertex has exactly one color has been studied for well o

An upper bound for the k-domination numb

An upper bound for the k-domination number of a graph

✍ E. J. Cockayne; B. Gamble; B. Shepherd 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 82 KB 👁 2 views

The kdomination number of a graph G, y k ( G ) , is the least cardinality of a set U of verticies such that any other vertex is adjacent to at least k vertices of U. We prove that if each vertex has degree at least k. then YAG) 5 kp/(k + 1).