On the chromatic index of join graphs and triangle-free graphs with large maximum degree

DOI10.1016/j.dam.2016.10.022zbMath1387.05101OpenAlexW2553106345MaRDI QIDQ1752497

A. Zorzi, Leandro M. Zatesko

Publication date: 24 May 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2016.10.022

zbMATH Keywords

edge-colouringoverfull conjecturejoin graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Vertex degrees (05C07)

Related Items (2)

Edge-colouring graphs with bounded local degree sums ⋮ Graph edge coloring: a survey

Cites Work

• Unnamed Item
• On the chromatic index of cographs and join graphs
• Decompositions for edge-coloring join graphs and cobipartite graphs
• Complement reducible graphs
• NP-completeness of edge-colouring some restricted graphs
• Méthode et théorème général de coloration des aretes d'un multigraphe
• How to find overfull subgraphs in graphs with large maximum degree
• The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3
• How to find overfull subgraphs in graphs with large maximum degree. II
• Quasi-threshold graphs
• Edge-colouring of joins of regular graphs. II
• Chromatic index of graphs with no cycle with a unique chord
• Edge-colouring of join graphs
• Linear time algorithms for graph search and connectivity determination on complement graphs.
• A Linear Recognition Algorithm for Cographs
• Graphs which are vertex-critical with respect to the edge-chromatic number
• Four classes of perfectly orderable graphs
• The chromatic index of graphs with a spanning star
• The NP-Completeness of Edge-Coloring
• The chromatic index of complete multipartite graphs
• The chromatic index of graphs of even order with many edges

This page was built for publication: On the chromatic index of join graphs and triangle-free graphs with large maximum degree