Back to Search
Start Over
The average degree of an edge-chromatic critical graph
- Source :
- Discrete Mathematics. 308(5-6):803-819
- Publication Year :
- 2008
- Publisher :
- Elsevier BV, 2008.
-
Abstract
- A graph G with maximum degree @D and edge chromatic number @g^'(G)>@D is [email protected] if @g^'(G-e)[email protected] for every edge e of G. New lower bounds are given for the average degree of an [email protected] graph, which improve on the best bounds previously known for most values of @D. Examples of [email protected] graphs are also given. In almost all cases, there remains a large gap between the best lower bound known and the smallest average degree of any known [email protected] graph.
- Subjects :
- Discrete mathematics
Degree (graph theory)
Critical graph
Edge colouring
Adjacency lemma
Edge-critical graph
Butterfly graph
Theoretical Computer Science
Combinatorics
Windmill graph
Graph power
Cubic graph
Discrete Mathematics and Combinatorics
Regular graph
Bound graph
MathematicsofComputing_DISCRETEMATHEMATICS
Mathematics
Subjects
Details
- ISSN :
- 0012365X
- Volume :
- 308
- Issue :
- 5-6
- Database :
- OpenAIRE
- Journal :
- Discrete Mathematics
- Accession number :
- edsair.doi.dedup.....6bf9e34725fdb5e9f8faa842b99fa601
- Full Text :
- https://doi.org/10.1016/j.disc.2007.07.048