Edge-colouring of regular graphs of large degree

DOI10.1016/J.TCS.2007.07.046MaRDI QIDQ2465629zbMATH OpenOpenAlexFDO

Authors Caterina De Simone, A. Galluccio

Publication date 7 January 2008

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2007.07.046

zbMATH Keywords

joinregular graphedge-colouring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Edge coloring regular graphs of high degree
• Regular Graphs of High Degree are 1-Factorizable
• Edge-colouring of joins of regular graphs. II
• Edge-colouring of joins of regular graphs. I
• Regular graphs and edge chromatic number

Cites work

• scientific article; zbMATH DE number 4132188 (Why is no real title available?)
• 25 pretty graph colouring problems
• A Linear Recognition Algorithm for Cographs
• Class 1 conditions depending on the minimum degree and the number of vertices of maximum degree
• Complement reducible graphs
• Edge coloring regular graphs of high degree
• Edge-colouring of join graphs
• Investigations on an edge coloring problem
• Normal hypergraphs and the perfect graph conjecture
• On certain polytopes associated with graphs
• Regular Graphs of High Degree are 1-Factorizable
• The NP-Completeness of Edge-Coloring
• The Solution of a Timetabling Problem
• The chromatic index of complete multipartite graphs
• The chromatic index of graphs with large maximum degree, where the number of vertices of maximum degree is relatively small

Cited in

(19)

• Optimal edge coloring of large graphs
• Regular graphs and edge chromatic number
• Edge-colorings of some large graphs on alphabets
• Enumerating the edge-colourings and total colourings of a regular graph
• The P versus NP-complete dichotomy of some challenging problems in graph theory
• Edge-colouring graphs with bounded local degree sums
• The hardness of recognising poorly matchable graphs and the hunting of the \(d\)-snark
• Edge Colorings and Circular Flow Numbers of Regular Graphs
• Edge-colouring seven-regular planar graphs
• Edge-colouring eight-regular planar graphs
• A graph coloring problem
• Edge-colouring of joins of regular graphs. II
• Chromatic index of graphs with no cycle with a unique chord
• Edge-colouring of joins of regular graphs. I
• Edge-coloring critical graphs with high degree
• A Combinatorial Algorithm to Optimally Colour the Edges of the Graphs That Are Join of Regular Graphs
• Amalgamations of almost regular edge-colourings of simple graphs
• A conjecture on edge coloring of graphs
• The number of disjoint perfect matchings in semi-regular graphs

This page was built for publication: Edge-colouring of regular graphs of large degree

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