Edge-colouring of join graphs

DOI10.1016/j.tcs.2005.12.010zbMath1086.05028OpenAlexW2075352817MaRDI QIDQ2369004

Caterina De Simone, Célia Picinin de Mello

Publication date: 28 April 2006

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

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

zbMATH Keywords

Edge-colouringsJoin graphsOverfull graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (15)

The number of disjoint perfect matchings in semi-regular graphs ⋮ Edge-colouring of joins of regular graphs. I ⋮ On the chromatic index of cographs and join graphs ⋮ Edge-colouring and total-colouring chordless graphs ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ Edge-colouring graphs with bounded local degree sums ⋮ Sufficient conditions for a graph to be edge-colorable with maximum degree colors ⋮ On the edge chromatic vertex stability number of graphs ⋮ Edge-colouring of joins of regular graphs. II ⋮ Edge-colouring of regular graphs of large degree ⋮ On the chromatic index of join graphs and triangle-free graphs with large maximum degree ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ Chromatic index of graphs with no cycle with a unique chord ⋮ Decompositions for edge-coloring join graphs and cobipartite graphs ⋮ A Combinatorial Algorithm to Optimally Colour the Edges of the Graphs That Are Join of Regular Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The chromatic index of graphs with large maximum degree, where the number of vertices of maximum degree is relatively small
• The chromatic index of graphs with large maximum degree
• Critical star multigraphs
• NP-completeness of edge-colouring some restricted graphs
• Edge coloring regular graphs of high degree
• How to find overfull subgraphs in graphs with large maximum degree. II
• Class 1 conditions depending on the minimum degree and the number of vertices of maximum degree
• Graphs which are vertex-critical with respect to the edge-chromatic number
• The chromatic index of graphs with a spanning star
• The NP-Completeness of Edge-Coloring
• Odd Minimum Cut-Sets and b-Matchings
• The chromatic index of complete multipartite graphs
• Regular Graphs of High Degree are 1-Factorizable
• The Solution of a Timetabling Problem

This page was built for publication: Edge-colouring of join graphs