Maximal edge colorings of graphs

DOI10.1016/J.EJC.2023.103824MaRDI QIDQ6181990zbMATH OpenOpenAlexFDO

Authors Sebastian Babiński, A. Grzesik

Publication date 23 January 2024

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.09538

Mathematics Subject Classification ID

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

Abstract: For a graph $G$ of order $n$ a maximal edge coloring is a proper edge coloring with $ch{i}^{\prime }(K_n)$ colors such that adding any edge to $G$ in any color makes it improper. Meszka and Tyniec proved that for some values of the number of edges there are no graphs with a maximal edge coloring, while for some other values, they provided constructions of such graphs. However, for many values of the number of edges determining whether there exists any graph with a maximal edge coloring remained open. We give a complete solution of this problem.

Recommendations

• Maximal edge-colorings of graphs
• Maximal edge-colorings of graphs
• Maximum edge-colorings of graphs
• On the maximal colorings of complete graphs without some small properly colored subgraphs
• \(M_i\)-edge colorings of graphs

Cites work

• scientific article; zbMATH DE number 6473829 (Why is no real title available?)
• scientific article; zbMATH DE number 426166 (Why is no real title available?)
• scientific article; zbMATH DE number 3468893 (Why is no real title available?)
• scientific article; zbMATH DE number 637270 (Why is no real title available?)
• Maximal designs and configurations -- a survey
• Maximal edge-colorings of graphs
• Maximal partial Latin cubes
• Maximal sets of 2-factors and Hamiltonian cycles
• On-line edge-coloring with a fixed number of colors
• The greedy algorithm is optimal for on-line edge coloring
• The spectrum of maximal sets of one-factors

Cited in

(1)

• Maximal edge-colorings of graphs

This page was built for publication: Maximal edge colorings of graphs

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