𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Lower bound of cyclic edge connectivity for n-extendability of regular graphs

✍ Scribed by Dingjun Lou; D.A. Holton

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
701 KB
Volume
112
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A cyclically m-edge-connected n-connected k-regular graph is called an (m.n.k) graph. It is proved that for any m > 0 and k 2 3, there is an (m, k, k) bipartite graph. A graph G is n-extendable if every matching of size n in G lies in a perfect matching of G. We prove the existence of a (k2-1, k + 1, k + 1) bipartite graph which is not k-extendable and the existence of an (m, k + 1, k + 1) graph which is not n-extendable, where n82, k>2 and m is any positive integer. The existence of the former graphs shows that a result of Holton and Plummer is sharp.

πŸ“œ SIMILAR VOLUMES

New lower bounds for the size of edge ch
New lower bounds for the size of edge chromatic critical graphs
✍ Yue Zhao πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 108 KB πŸ‘ 1 views

## Abstract In this paper, by applying the discharging method, we obtain new lower bounds for the size of edge chromatic critical graphs for small maximum degree Ξ”. Β© 2004 Wiley Periodicals, Inc. J Graph Theory 46: 81–92, 2004

A general upper bound for the cyclic chr
A general upper bound for the cyclic chromatic number of 3-connected plane graphs
✍ Hikoe Enomoto; Mirko HorňÑk πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 457 KB πŸ‘ 1 views

## Abstract The cyclic chromatic number of a plane graph __G__ is the smallest number Ο‡~__c__~(__G__) of colors that can be assigned to vertices of __G__ in such a way that whenever two distinct vertices are incident with a common face, they receive distinct colors. It was conjectured by Plummer an