𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Some upper bounds on the total and list chromatic numbers of multigraphs

✍ Scribed by Roland Häggkvist; Amanda Chetwynd

Publisher
John Wiley and Sons
Year
1992
Tongue
English
Weight
762 KB
Volume
16
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this paper we discuss some estimates for upper bounds on a number of chromatic parameters of a multigraph. In particular, we show that the total chromatic number for an n‐order multigraph exceeds the chromatic index by the smallest t such that t! > n.

📜 SIMILAR VOLUMES

An upper bound for the total chromatic n
An upper bound for the total chromatic number of dense graphs
✍ H. R. Hind 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 340 KB 👁 1 views

## Abstract In this paper we consider those graphs that have maximum degree at least 1/__k__ times their order, where __k__ is a (small) positive integer. A result of Hajnal and Szemerédi concerning equitable vertex‐colorings and an adaptation of the standard proof of Vizing's Theorem are used to s

Some upper bounds for the product of the
Some upper bounds for the product of the domination number and the chromatic number of a graph
✍ Jerzy Topp; Lutz Volkmann 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 199 KB

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 consider

On an upper bound for the harmonious chr
On an upper bound for the harmonious chromatic number of a graph
✍ Zhikang Lu 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 2 views

## Abstract The upper bound for the harmonious chromatic number of a graph that has been given by Sin‐Min Lee and John Mitchem is improved.

On some simple degree conditions that gu
On some simple degree conditions that guarantee the upper bound on the chromatic (choice) number of random graphs
✍ Vu, Van H. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 318 KB 👁 2 views

It is well known that almost every graph in the random space G(n, p) has chromatic number of order O(np/ log(np)), but it is not clear how we can recognize such graphs without eventually computing the chromatic numbers, which is NP-hard. The first goal of this article is to show that the above-menti