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

A note on upper bounds for the maximum span in interval edge-colorings of graphs

โœ Scribed by R.R. Kamalian; P.A. Petrosyan

Book ID
113567569
Publisher
Elsevier Science
Year
2012
Tongue
English
Weight
538 KB
Volume
312
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

An upper bound on the number of edges of
An upper bound on the number of edges of edge-coloring critical graphs with high maximum degree
โœ Lian-ying Miao; Shi-you Pang; Jian-liang Wu ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 100 KB

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.

A sharp upper bound for the number of st
A sharp upper bound for the number of stable sets in graphs with given number of cut edges
โœ Hongbo Hua ๐Ÿ“‚ Article ๐Ÿ“… 2009 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 648 KB

Let G be a connected and simple graph, and let i(G) denote the number of stable sets in G. In this letter, we have presented a sharp upper bound for the i(G)-value among the set of graphs with k cut edges for all possible values of k, and characterized the corresponding extremal graphs as well.

Tight upper bound on the number of edges
Tight upper bound on the number of edges in a bipartite K3,3-free or K5-free graph with an application
โœ Zhi-Zhong Chen; Shiqing Zhang ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 68 KB

We show that an n-vertex bipartite K 3,3 -free graph with n 3 has at most 2n -4 edges and that an n-vertex bipartite K 5 -free graph with n 5 has at most 3n -9 edges. These bounds are also tight. We then use the bound on the number of edges in a K 3,3 -free graph to extend two known NC algorithms fo