𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the size of edge-coloring critical graphs with maximum degree 4

✍ Scribed by Lianying Miao; Shiyou Pang

Book ID
108113937
Publisher
Elsevier Science
Year
2008
Tongue
English
Weight
187 KB
Volume
308
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Acyclic edge coloring of graphs with max
Acyclic edge coloring of graphs with maximum degree 4
✍ Manu Basavaraju; L. Sunil Chandran πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 168 KB πŸ‘ 1 views

## Abstract An __acyclic__ edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The __acyclic chromatic index__ of a graph is the minimum number __k__ such that there is an acyclic edge coloring using __k__ colors and is denoted by __a__β€²(__G__). It was conj

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

Edge-face coloring of plane graphs with
Edge-face coloring of plane graphs with maximum degree nine
✍ Jean-SΓ©bastien Sereni; MatΔ›j StehlΓ­k πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 189 KB πŸ‘ 1 views

An edge-face coloring of a plane graph with edge set E and face set F is a coloring of the elements of E βˆͺF so that adjacent or incident elements receive different colors. Borodin [Discrete Math 128(1-3): [21][22][23][24][25][26][27][28][29][30][31][32][33] 1994] proved that every plane graph of max

4-edge-coloring graphs of maximum degree
4-edge-coloring graphs of maximum degree 3 in linear time
✍ San Skulrattanakulchai πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 65 KB

We present a linear time algorithm to properly color the edges of any graph of maximum degree 3 using 4 colors. Our algorithm uses a greedy approach and utilizes a new structure theorem for such graphs.

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.