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

DOI10.1016/J.DAM.2016.10.022MaRDI QIDQ1752497zbMATH OpenOpenAlexFDO

Authors 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-colouringjoin graphsoverfull conjecture

Mathematics Subject Classification ID

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

Recommendations

• On the chromatic index of cographs and join graphs
• The chromatic index of graphs with large maximum degree, where the number of vertices of maximum degree is relatively small
• On the chromatic number of triangle-free graphs of large minimum degree
• On the chromatic index of multigraphs without large triangles
• The chromatic index of graphs of high maximum degree
• The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3
• scientific article; zbMATH DE number 4122017
• Triangle-free graphs with large chromatic numbers
• The total chromatic number of graphs having large maximum degree
• On the chromatic index of almost all graphs

Cites work

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

Cited in

(7)

• The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3
• Graph edge coloring: a survey
• Edge-colouring graphs with bounded local degree sums
• On the chromatic index of cographs and join graphs
• The hardness of recognising poorly matchable graphs and the hunting of the \(d\)-snark
• On the chromatic index of multigraphs without large triangles
• Decompositions for edge-coloring join graphs and cobipartite graphs

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

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