๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An upper bound on the number of edges of edge-coloring critical graphs with high maximum degree

โœ Scribed by Lian-ying Miao; Shi-you Pang; Jian-liang Wu

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
100 KB
Volume
271
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

In this paper, we prove that any edge-coloring critical graph G with maximum degree ยฟ (11 + โˆš 49 -24 )=2, where 6 1, has the size at least 3(|V (G)| -) + 1 if 6 7 or if ยฟ 8 and |V (G)| ยฟ 2 --4 -( + 6)=( -6), where is the minimum degree of G. It generalizes a result of Sanders and Zhao.

๐Ÿ“œ SIMILAR VOLUMES

The maximum number of edges in a graph w
The maximum number of edges in a graph with fixed edge-degree
โœ R.J. Faudree; J. Sheehan ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 633 KB

Suppose that n i> 2t + 2 (t/> 17). Let G be a graph with n vertices such that its complement is connected and, for all distinct non-adjacent vertices u and v, there are at least t common neighbours. Then we prove that and Furthermore, the results are sharp.

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 number of edges in 2K2-free
The maximum number of edges in 2K2-free graphs of bounded degree
โœ F.R.K. Chung; A. Gyรกrfรกs; Z. Tuza; W.T. Trotter ๐Ÿ“‚ Article ๐Ÿ“… 1990 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 481 KB

A graph is 2K,-free if it does not contain an independent pair of edges as an induced subgraph. We show that if G is 2K,-free and has maximum degree A(G) = D, then G has at most 5D2/4 edges if D is even. If D is odd, this bound can be improved to (5D\* -20 + 1)/4. The extremal graphs are unique.

A new upper bound for the independence n
A new upper bound for the independence number of edge chromatic critical graphs
โœ Rong Luo; Yue Zhao ๐Ÿ“‚ Article ๐Ÿ“… 2010 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 107 KB ๐Ÿ‘ 2 views

In 1968, Vizing conjectured that if G is a -critical graph with n vertices, then (G) โ‰ค n / 2, where (G) is the independence number of G. In this paper, we apply Vizing and Vizing-like adjacency lemmas to this problem and prove that (G)<(((5 -6)n) / (8 -6))<5n / 8 if โ‰ฅ 6. แญง 2010 Wiley

An improved edge bound on the interval n
An improved edge bound on the interval number of a graph
โœ Jeremy R. Spinrad; G. Vijayan; Douglas B. West ๐Ÿ“‚ Article ๐Ÿ“… 1987 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 147 KB ๐Ÿ‘ 2 views

The upper bound on the interval number of a graph in terms of its number of edges is improved. Also, the interval number of graphs in hereditary classes is bounded in terms of the vertex degrees. A representation of a graph as an intersection graph assigns each vertex a set such that vertices are a