𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Sizes of graphs with induced subgraphs of large maximum degree

✍ Scribed by Paul Erdős; Talmage James Reid; Richard Schelp; William Staton

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
249 KB
Volume
158
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Graphs with n + k vertices in which every set of n +j vertices induce a subgraph of maximum degree at least n are considered.

For j = 1 and for k fairly small compared to n, we determine the minimum number of edges in such graphs.

📜 SIMILAR VOLUMES

Total colorings of planar graphs with la
Total colorings of planar graphs with large maximum degree
✍ Borodin, O. V.; Kostochka, A. V.; Woodall, D. R. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB 👁 3 views

It is proved that a planar graph with maximum degree ∆ ≥ 11 has total (vertex-edge) chromatic number ∆ + 1.

The chromatic index of graphs with large
The chromatic index of graphs with large maximum degree
✍ Michael J. Plantholt 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 508 KB

Vizing's Theorem, any graph G has chromatic index equal either to its maximum degree A(G) or A(G) + 1. A simple method is given for determining exactly the chromatic index of any graph with 2s + 2 vertices and maximum degree 2s.

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

The maximum size of graphs satisfying a
The maximum size of graphs satisfying a degree condition
✍ Yiping Qiu; Xiao Feng Jia 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 196 KB

Let G be a simple graph of order n without isolated vertices. If the integer h satisfies In this note the maximum size of Sri(h)--graphs is determined. A result of Krol and Veldman on critically h-connected graphs follows as a corollary.

The total chromatic number of graphs hav
The total chromatic number of graphs having large maximum degree
✍ A.J.W. Hilton; H.R. Hind 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 935 KB

Hilton, A.J.W. and H.R. Hind, The total chromatic number ofgraphs having large maximum degree, Discrete Mathematics 117 (1993) 127-140. The total colouring conjecture is shown to be correct for those graphs G having d(G)>21 V(G)I.

Vertex decompositions of sparse graphs i
Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k
✍ O. V. Borodin; A. O. Ivanova; M. Montassier; P. Ochem; A. Raspaud 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract A graph __G__ is (__k__,0)‐colorable if its vertices can be partitioned into subsets __V__~1~ and __V__~2~ such that in __G__[__V__~1~] every vertex has degree at most __k__, while __G__[__V__~2~] is edgeless. For every integer __k__⩾0, we prove that every graph with the maximum average