Asymptotics of the chromatic index for multigraphs

DOI10.1006/JCTB.1996.0067zbMATH Open0861.05026OpenAlexW2044004462MaRDI QIDQ1125951FDOQ1125951

J. Kahn

Publication date: 19 May 1997

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jctb.1996.0067

zbMATH Keywords

multigraphhypergraphsmaximum degreecoloringschromatic indexmatching polytopefractional chromatic indexhard-core distributionsincremental -random method

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (28)

• Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design
• Chromatic index determined by fractional chromatic index
• Extension from precoloured sets of edges
• Edge coloring nearly bipartite graphs
• Goldberg's conjecture is true for random multigraphs
• A characterization of graphs with fractional total chromatic number equal to \(\Delta +2\)
• Edge coloring multigraphs without small dense subsets
• Fractional v. integral covers in hypergraphs of bounded edge size
• On a limit of the method of Tashkinov trees for edge-colouring
• Two Chromatic Conjectures: One for Vertices and One for Edges
• Randomly colouring graphs (a combinatorial view)
• Title not available (Why is that?)
• Efficiently list‐edge coloring multigraphs asymptotically optimally
• Graph edge colouring: Tashkinov trees and Goldberg's conjecture
• On the stochastic independence properties of hard-core distributions
• Approximating the chromatic index of multigraphs
• Graph and hypergraph colouring via nibble methods: a survey
• The parameterised complexity of list problems on graphs of bounded treewidth
• An upper bound for the chromatic number of line graphs
• A superlocal version of Reed's conjecture
• A sublinear bound on the chromatic index of multigraphs
• Title not available (Why is that?)
• Asymptotics of the chromatic number for quasi-line graphs
• Set Covering with Ordered Replacement: Additive and Multiplicative Gaps
• A Combined Logarithmic Bound on the Chromatic Index of Multigraphs
• The chromatic index of multigraphs that are nearly full
• Graph edge coloring: a survey
• A unified approach to distance-two colouring of graphs on surfaces

This page was built for publication: Asymptotics of the chromatic index for multigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1125951)