𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An upper bound for total colouring of graphs

✍ Scribed by Colin J.H. McDiarmid; Abdón Sánchez-Arroyo

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
235 KB
Volume
111
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

An upper bound for total colouring of graphs, Discrete Mathematics 111 (1993) 3899392.

We give an upper bound on the number of colours required to extend a given vertex colouring of a graph to a total colouring. This shows that for any simple graph there is a total colouring using at most :d + 3 colours, where A is the maximum vertex degree.

📜 SIMILAR VOLUMES

A new upper bound for total colourings o
A new upper bound for total colourings of graphs
✍ Abdón Sánchez-Arroyo 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 118 KB

We give a new upper bound on the total chromatic number of a graph. This bound improves the results known for some classes of graphs. The bound is stated as follows: ZT ~< Z~ + L l3 ~ J + 2, where Z is the chromatic number, Z~ is the edge chromatic number (chromatic index) and ZT is the total chroma

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

An upper bound for the path number of a
An upper bound for the path number of a graph
✍ Alan Donald 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 529 KB

## Abstract The path number of a graph __G__, denoted __p(G)__, is the minimum number of edge‐disjoint paths covering the edges of __G.__ Lovász has proved that if __G__ has __u__ odd vertices and __g__ even vertices, then __p(G)__ ≤ 1/2 __u__ + __g__ ‐ 1 ≤ __n__ ‐ 1, where __n__ is the total numbe

On equality in an upper bound for domina
On equality in an upper bound for domination parameters of graphs
✍ Favaron, O.; Mynhardt, C. M. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 141 KB 👁 2 views

We consider the well-known upper bounds µ(G) ≤ |V (G)|-∆(G), where ∆(G) denotes the maximum degree of G and µ(G) the irredundance, domination or independent domination numbers of G and give necessary and sufficient conditions for equality to hold in each case. We also describe specific classes of gr

An upper bound for orders of certain (k,
An upper bound for orders of certain (k, k))-connected graphs
✍ Kiyoshi Ando 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 275 KB

A fragment of a connected graph G is a subset A of V(C) consisting of components of G-S such that V(G)-S-A #0 where S is a minimum cut of G. A graph G is said to be (k, I;)- We prove the following result. Let k and k be integers with 1 <i < k, and let G be a critically (k, k)-connected graph. If no

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