Edge-colouring of regular graphs of large degree

DOI10.1016/j.tcs.2007.07.046zbMath1143.05026OpenAlexW1980938219MaRDI QIDQ2465629

Anna Galluccio, Caterina De Simone

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

joinedge-colouringregular graph

Mathematics Subject Classification ID

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

Related Items

The number of disjoint perfect matchings in semi-regular graphs, Edge-colouring of joins of regular graphs. I, Edge-colouring graphs with bounded local degree sums, Edge-colouring of joins of regular graphs. II, The P versus NP-complete dichotomy of some challenging problems in graph theory, Chromatic index of graphs with no cycle with a unique chord, A Combinatorial Algorithm to Optimally Colour the Edges of the Graphs That Are Join of Regular Graphs

Cites Work

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