✦ LIBER ✦

New upper bounds on harmonious colorings

✍ Scribed by Keith Edwards; Colin McDiarmid

Publisher: John Wiley and Sons
Year: 1994
Tongue: English
Weight: 435 KB
Volume: 18
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190180305

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We present an improved upper bound on the harmonious chromatic number of an arbitrary graph. We also consider „fragmentable”︁ classes of graphs (an example is the class of planar graphs) that are, roughly speaking, graphs that can be decomposed into bounded‐sized components by removing a small proportion of the vertices. We show that for such graphs of bounded degree the harmonious chromatic number is close to the lower bound (2__m__)^1/2^, where m is the number of edges.

📜 SIMILAR VOLUMES

Upper bounds for harmonious colorings

✍ Colin McDiarmid; Luo Xinhua 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 301 KB

## Abstract A harmonious coloring of a simple graph __G__ is a coloring of the vertices such that adjacent vertices receive distinct colors and each pair of colors appears together on at most one edge. The harmonious chromatic number __h__(__G__) is the least number of colors in such a coloring. We

A new upper bound for the harmonious chr

A new upper bound for the harmonious chromatic number

✍ Edwards, Keith 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 200 KB 👁 2 views

A harmonious coloring of a simple graph G is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number h(G) is the least number of colors in such a coloring. We obtain a new upper bound for the harmonious chromatic number of general

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.

New upper bounds for the greatest number

New upper bounds for the greatest number of proper colorings of a (V,E)-graph

✍ Felix Lazebnik 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 185 KB

## Abstract Let 𝒻 denote the family of simple undirected graphs on __v__ vertices having __e__ edges ((__v__, __e__)‐graphs) and __P__(__G__; λ) be the chromatic polynomial of a graph __G.__ For the given integers __v__, __e__, and λ, let __f__(__v__, __e__, λ) denote the greatest number of proper

New upper bounds on the decomposability

New upper bounds on the decomposability of planar graphs

✍ Fedor V. Fomin; Dimitrios M. Thilikos 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 335 KB 👁 1 views

## Abstract It is known that a planar graph on __n__ vertices has branch‐width/tree‐width bounded by $\alpha \sqrt {n}$. In many algorithmic applications, it is useful to have a small bound on the constant α. We give a proof of the best, so far, upper bound for the constant α. In particular, for th

New Upper Bounds for Maximum Satisfiabil

New Upper Bounds for Maximum Satisfiability

✍ Rolf Niedermeier; Peter Rossmanith 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 168 KB

The unweighted Maximum Satisfiability problem MAXSAT is: Given a Boolean formula in conjunctive normal form, find a truth assignment that satisfies the largest number of clauses. This paper describes exact algorithms that provide new Ž< < upper bounds for MAXSAT. We prove that MAXSAT can be solved i