𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Fair reception and Vizing's conjecture

✍ Scribed by Boštjan Brešar; Douglas F. Rall

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
150 KB
Volume
61
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this paper we introduce the concept of fair reception of a graph which is related to its domination number. We prove that all graphs G with a fair reception of size γ(G) satisfy Vizing's conjecture on the domination number of Cartesian product graphs, by which we extend the well‐known result of Barcalkin and German concerning decomposable graphs. Combining our concept with a result of Aharoni, Berger and Ziv, we obtain an alternative proof of the theorem of Aharoni and Szabó that chordal graphs satisfy Vizing's conjecture. A new infinite family of graphs that satisfy Vizing's conjecture is also presented. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 45‐54, 2009

📜 SIMILAR VOLUMES

Vizing's conjecture: a survey and recent
Vizing's conjecture: a survey and recent results
✍ Boštjan Brešar,; Paul Dorbec,; Wayne Goddard,; Bert L. Hartnell,; Michael A. Hen 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 380 KB

## Abstract Vizing's conjecture from 1968 asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. In this paper we survey the approaches to this central conjecture from domination theory and give some new results alo

A partition approach to Vizing's conject
A partition approach to Vizing's conjecture
✍ Chen, Guantao; Piotrowski, Wiktor; Shreve, Warren 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 411 KB 👁 1 views

In 1963, Vizing [Vichysl. Sistemy 9 (19631, 30-431 conjectured that y ( G X H) 2 y ( G ) y ( H ) , where G X Hdenotes the Cartesian product of graphs, and y(G) is the domination number. In this paper we define the extraction number x(G) and w e prove that ## M G ) 5 x(G) 5 y(G), and y ( G x H) 2 x

Vizing's coloring algorithm and the fan
Vizing's coloring algorithm and the fan number
✍ Diego Scheide; Michael Stiebitz 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 199 KB

## Abstract Most upper bounds for the chromatic index of a graph come from algorithms that produce edge colorings. One such algorithm was invented by Vizing [Diskret Analiz 3 (1964), 25–30] in 1964. Vizing's algorithm colors the edges of a graph one at a time and never uses more than Δ+µ colors, wh

Subcontraction-equivalence and Hadwiger'
Subcontraction-equivalence and Hadwiger's conjecture
✍ D. R. Woodall 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 350 KB

The concept of subcontraction-equivalence is defined, and 14 graphtheoretic properties are exhibited that are all subcontraction-equivalent if Hadwiger's conjecture is true. Some subsets of these properties are proved to be subcontraction-equivalent anyway. Hadwiger's conjecture is expressed as the