✦ LIBER ✦

Sizes of Critical Graphs with Small Maximum Degrees

✍ Scribed by Xuechao Li

Publisher: Springer Japan
Year: 2006
Tongue: English
Weight: 136 KB
Volume: 22
Category: Article
ISSN: 0911-0119
DOI: 10.1007/s00373-006-0679-7

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

Sizes of graphs with induced subgraphs o

Sizes of graphs with induced subgraphs of large maximum degree

✍ Paul Erdős; Talmage James Reid; Richard Schelp; William Staton 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 249 KB

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.

Minimally Non-Preperfect Graphs of Small

Minimally Non-Preperfect Graphs of Small Maximum Degree

✍ Zsolt Tuza; Annegret Wagler 📂 Article 📅 2001 🏛 Springer Japan 🌐 English ⚖ 145 KB

Primal graphs with small degrees

✍ Phyllis Z. Chinn; R.Bruce Richter; Miroslaw Truszczynski 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 746 KB

## It has previously been shown that there is a unique set Il of primal graphs such that every graph has an edge-decomposition into non-isomorphic elements of 17 and that the only decomposition of an element of II into non-isomorphic elements of II is the obvious one. Here it is shown that there a

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.

Size and independence in triangle-free g

Size and independence in triangle-free graphs with maximum degree three

✍ Kathryn Fraughnaugh Jones 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 549 KB

## Abstract Let __C__ be the class of triangle‐free graphs with maximum degree at most three. A lower bound for the number of edges in a graph of __C__ is derived in terms of the number of vertices and the independence. Several classes of graphs for which this bound is attained are given. As coroll