Edge coloring regular graphs of high degree

DOI10.1016/S0012-365X(96)00202-6MaRDI QIDQ1356779zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Ljubomir Perković, Bruce Reed

Publication date 15 December 1998

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(96)00202-6

zbMATH Keywords

1-factorchromatic indexedge-coloringregular graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

There is an old conjecture to the effect that if \(G= (V, E)\) is a \(\Delta\)-regular simple graph of even order with \(| V|\leq 2\Delta\), then \(G\) is 1-factorizable. The authors show that this conjecture is true for large graphs with \(| V|<(2-\varepsilon)\Delta\) where \(\varepsilon> 0\). The proof is constructive and implies an algorithm for \(\Delta\)-edge-colorings of such graphs. This result improves that of \textit{A. G. Chetwynd} and \textit{A. J. W. Hilton} [1-factorizing regular graphs of high degree---an improved bound, Discrete Math. 75, No. 1-3, 103-112 (1989; Zbl 0675.05030)] for simple \(\Delta\)-regular graphs with \(\Delta\geq .5(\sqrt 7-1)| V|\).

Recommendations

• Edge-colouring of regular graphs of large degree
• Regular Graphs of High Degree are 1-Factorizable
• Edge coloring graphs with large minimum degree
• Two conjectures on edge-colouring
• Regular Multigraphs of High Degree are 1-Factorizable

Cites work

• 1-factorizing regular graphs of high degree - an improved bound
• 25 pretty graph colouring problems
• Graphs which are vertex-critical with respect to the edge-chromatic number
• scientific article; zbMATH DE number 3427408 (Why is no real title available?)
• scientific article; zbMATH DE number 3428958 (Why is no real title available?)
• Regular Graphs of High Degree are 1-Factorizable
• The chromatic index of graphs with large maximum degree, where the number of vertices of maximum degree is relatively small

Cited in

(25)

• An application of Tutte's theorem to 1-factorization of regular graphs of high degree
• Edge coloring nearly bipartite graphs
• Graph edge coloring: a survey
• Edge-coloring critical graphs with high degree
• Edge-colouring of joins of regular graphs. II
• Explicit \(\Delta \)-edge-coloring of consecutive levels in a divisor lattice
• The chromatic index of graphs with large even order \(n\) and minimum degree at least \(2n/3\)
• Regular colorings in regular graphs
• Number of 1-factorizations of regular high-degree graphs
• Edge-colouring of join graphs
• Hamilton decompositions of regular expanders: applications
• Edge-colouring of regular graphs of large degree
• Regular Multigraphs of High Degree are 1-Factorizable
• Edge-colouring eight-regular planar graphs
• The number of disjoint perfect matchings in semi-regular graphs
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• A Combinatorial Algorithm to Optimally Colour the Edges of the Graphs That Are Join of Regular Graphs
• Edge coloring graphs with large minimum degree
• Further split graphs known to be class 1 and a characterization of subgraph-overfull split graphs
• The hardness of recognising poorly matchable graphs and the hunting of the \(d\)-snark
• On the multigraph overfull conjecture
• Towards the overfull conjecture
• Regular graphs and edge chromatic number
• Edge-colouring of joins of regular graphs. I
• Graph factors and factorization: 1985--2003: a survey

This page was built for publication: Edge coloring regular graphs of high degree

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