Maximal edge colorings of graphs

DOI10.1016/J.EJC.2023.103824arXiv1912.09538OpenAlexW2996182638MaRDI QIDQ6181990FDOQ6181990

A. Grzesik, Sebastian Babiński

Publication date: 23 January 2024

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

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.

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)

Cites Work

• The greedy algorithm is optimal for on-line edge coloring
• Maximal designs and configurations -- a survey
• Maximal partial Latin cubes
• Maximal sets of 2-factors and Hamiltonian cycles
• Title not available (Why is that?)
• On-line edge-coloring with a fixed number of colors
• Title not available (Why is that?)
• The spectrum of maximal sets of one-factors
• Maximal edge-colorings of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)

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)