✦ LIBER ✦

On the critical graph conjecture

✍ Scribed by Hian Poh Yap

Publisher: John Wiley and Sons
Year: 1980
Tongue: English
Weight: 222 KB
Volume: 4
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190040309

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Gol'dberg has recently constructed an infinite family of 3‐critical graphs of even order. We now prove that if there exists a p(≥4)‐critical graph K of odd order such that K has a vertex u of valency 2 and another vertex v ≠ u of valency ≤(p + 2)/2, then there exists a p‐critical graph of even order.

📜 SIMILAR VOLUMES

The rise and fall of the critical graph

The rise and fall of the critical graph conjecture

✍ Amanda G. Chetwynd; Robin J. Wilson 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB 👁 1 views

## Abstract In this expository paper we discuss the critical graph conjecture and its eventual disproof by M.K. Goldberg and others.

On the strong perfect graph conjecture

✍ Stephan Olariu 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 384 KB

A graph G is perfect if for every induced subgraph H of G the chromatic number x(H) equals the largest number w ( H ) of pairwise adjacent vertices in H. Berge's famous Strong Perfect Graph Conjecture asserts that a graph G is perfect if and only if neither G nor its complement C contains an odd cho

Proof of Mader's conjecture on k-critica

Proof of Mader's conjecture on k-critical n-connected graphs

✍ Su Jianji 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB 👁 1 views

## Abstract Mader conjectured that every __k__‐critical __n__‐connected noncomplete graph __G__ has __2k__ + 2 pairwise disjoint fragments. The author in 9 proved that the conjecture holds if the order of __G__ is greater than (__k__ + 2)__n__. Now we settle this conjecture completely. © 2004 Wiley

On critically perfect graphs

✍ Wagler, Annegret 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 337 KB 👁 2 views

A perfect graph is critical, if the deletion of any edge results in an imperfect graph. We give examples of such graphs and prove some basic properties. We relate critically perfect graphs to well-known classes of perfect graphs, investigate the structure of the class of critically perfect graphs, a

On the critical point-arboricity graphs

✍ Riste Škrekovski 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 155 KB

## Abstract In this paper, we study the critical point‐arboricity graphs. We prove two lower bounds for the number of edges of __k__‐critical point‐arboricity graphs. A theorem of Kronk is extended by proving that the point‐arboricity of a graph __G__ embedded on a surface __S__ with Euler genus __

On Deeply Critical Oriented Graphs

✍ O.V. Borodin; D. Fon-Der-Flaass; A.V. Kostochka; A. Raspaud; E. Sopena 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 96 KB

For every positive integer k, we present an oriented graph G k such that deleting any vertex of G k decreases its oriented chromatic number by at least k and deleting any arc decreases the oriented chromatic number of G k by two.