✦ LIBER ✦

A vertex critical graph without critical edges

✍ Scribed by Jason I. Brown

Publisher: Elsevier Science
Year: 1992
Tongue: English
Weight: 189 KB
Volume: 102
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)90354-i

No coin nor oath required. For personal study only.

✦ Synopsis

Brown, J.I., A vertical critical graph without critical edges, Discrete Mathematics 102 (1992) 99-101. A vertex k-critical graph is a k-chromatic graph with the property that the removal of any vertex leaves a (k -1)-colourable graph. A critical edge in a graph is an edge whose deletion lowers the chromatic number. Dirac conjectured

in 1970 that for some k 2 4 there is a vertex k-critical graph with no critical edge. We produce here an example of such a graph for k = 5.

📜 SIMILAR VOLUMES

Vertex domination-critical graphs

✍ Jason Fulman; Denis Hanson; Gary Macgillivray 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 293 KB

Vertex domination-critical graphs

✍ Robert C. Brigham; Phyllis Z. Chinn; Ronald D. Dutton 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 303 KB

Minimum vertex-diameter-2-critical graph

Minimum vertex-diameter-2-critical graphs

✍ Ya-Chen Chen; Zoltán Füredi 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 182 KB 👁 1 views

## Abstract We prove that the minimum number of edges in a vertex‐diameter‐2‐critical graph on __n__ ≥ 23 vertices is (5__n__ − 17)/2 if __n__ is odd, and is (5__n__/2) − 7 if __n__ is even. © 2005 Wiley Periodicals, Inc. J Graph Theory

Local edge domination critical graphs

✍ Michael A. Henning; Ortrud R. Oellermann; Henda C. Swart 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 521 KB

Sumner and Blitch defined a graph G to be k-y-critical if 7(G) = k and 7(G + uv) = k -1 for each pair u, v of nonadjacent vertices of G. We define a graph to be k-( 7,d)-critical if 7(G) = k and 7(G + uv) = k -I for each pair u, v of nonadjacent vertices of G that are at distance at most d apart. Th

On vertex critical graphs with prescribe

On vertex critical graphs with prescribed diameter

✍ L. Caccetta; S. EL-Batanouny; J. Huang 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB 👁 1 views

## Abstract Let __G__ be connected simple graph with diameter __d__(__G__). __G__ is said __v__^+^‐critical if __d__(__G__−__v__) is greater than __d__(__G__) for every vertex __v__ of __G__. Let D′ = max {__d__(__G__−__v__) : __v__ ∈ __V__(__G__)}. Boals et al. [Congressus Numerantium 72 (1990), 1

Vertex-splitting and chromatic index cri

Vertex-splitting and chromatic index critical graphs

✍ A.J.W. Hilton; C. Zhao 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 477 KB

We study graphs which are critical with respect to the chromatic index. We relate these to the Overfull Conjecture and we study in particular their construction from regular graphs by subdividing an edge or by splitting a vertex.