𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Vertices of degree 6 in a 6-contraction critical graph

✍ Scribed by Kiyoshi Ando; Atsushi Kaneko; Ken-ichi Kawarabayashi

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
229 KB
Volume
10
Category
Article
ISSN
1571-0653

No coin nor oath required. For personal study only.

✦ Synopsis

An edge of a (k)-connected graph is said to be (k)-contractible if the contraction of the edge results in a (k)-connected graph. A (k)-connected graph with no (k)-contractible edge is said to be a (k)-contraction critical graph. We prove that every 6 -contraction critical graph of order (n) has at least (n / 7) vertices of degree 6 .

πŸ“œ SIMILAR VOLUMES

Vertices of degree 6 in a contraction cr
Vertices of degree 6 in a contraction critically 6-connected graph
✍ Kiyoshi Ando; Atsushi Kaneko; Ken-ichi Kawarabayashi πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 378 KB

An edge of a 6-connected graph is said to be 6-contractible if the contraction of the edge results in a 6-connected graph. A contraction critically 6-connected graph is a 6-connected graph with no 6-contractible edge. We prove that each contraction critically 6-connected graph G has at least 1 7 |V

Vertices of given degree in a random gra
Vertices of given degree in a random graph
✍ BΓ©la BollobΓ‘s πŸ“‚ Article πŸ“… 1982 πŸ› John Wiley and Sons 🌐 English βš– 349 KB πŸ‘ 1 views
The size of edge chromatic critical grap
The size of edge chromatic critical graphs with maximum degree 6
✍ Rong Luo; Lianying Miao; Yue Zhao πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 216 KB πŸ‘ 1 views

## Abstract In 1968, Vizing [Uaspekhi Mat Nauk 23 (1968) 117–134; Russian Math Surveys 23 (1968), 125–142] conjectured that for any edge chromatic critical graph ${{G}} = ({{V}}, {{E}})$ with maximum degree $\Delta$, $|{{E}}| \geq {{{1}}\over {{2}}}\{(\Delta {{- 1}})|{{V}}| + {{3}}\}$. This conject