✦ LIBER ✦

Remarks on the critical graph conjecture

✍ Scribed by I. Broere; C.M. Mynhardt

Publisher: Elsevier Science
Year: 1979
Tongue: English
Weight: 344 KB
Volume: 26
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(79)90025-6

No coin nor oath required. For personal study only.

✦ Synopsis

The vertex-critical graph conjecture (critical graph conjecture respectively) states that every vertex-critical (critical) graph has an odd number of vertices. In this note we prove that if G is a critical graph of even order, then G has at least three vertices of less-than-maximum valency. In addition, if G is a 3-critical multigraph of smallest even order, then G is simple and has no triangles.

📜 SIMILAR VOLUMES

On the critical graph conjecture

✍ Hian Poh Yap 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 222 KB

## 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 ther

Remarks on the Jacobian Conjecture

✍ Jie-Tai Yu 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 118 KB

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.

A remark on Mulder's conjecture about in

A remark on Mulder's conjecture about interval-regular graphs

✍ K. Nomura 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 184 KB

Let F be a connected graph. F is said to be interval-regular if I F~\_ l(u) uF(x )J =. i holds for all vertices u and x ~ Fi(u), i > 0. For u, v e F, let I (u, v) denote the set of all vertices on a shortest path connecting u, v. A subset W of V(F) is said to be convex if l(u,v) c W holds for each u

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

On a harmonious graph conjecture

✍ Eugene Levine 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 125 KB

Let K~ ) be the umon of two complete graphs on n vertices which have preosely one vertex in common. Graham and Sloane have shown that K~ ~ is not harmomous for n od:~, /(~,~ is harmonious, and K~62~ is not harmonious. They also conjecture that K~' t,, not h,~rmomous except for n = 4. Here, it Is sho