×

The deficiency of a regular graph. (English) Zbl 1099.05037

Summary: A proper edge coloring \(c : E(G) \to \mathbb Z\) of a finite simple graph \(G\) is an interval coloring if the colors used at each vertex form a consecutive interval of integers. Many graphs do not have interval colorings, and the deficiency of a graph is an invariant that measures how close a graph comes to having an interval coloring. In this paper we search for tight upper bounds on the deficiencies of \(k\)-regular graphs in terms of the number of vertices. We find exact values for \(1\leqslant k \leqslant 4\) and bounds for larger \(k\).

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Asratian, A. S.; Kamalian, R. R., Interval colorings of the edges of a multigraph, Appl. Math., 5, 25-34 (1987), (in Russian) · Zbl 0805.05024
[2] Giaro, K., The complexity of consecutive \(\Delta \)-coloring of bipartite graphs: 4 is easy, 5 is hard, Ars Combin., 47, 287-298 (1997) · Zbl 0933.05050
[3] Giaro, K.; Kubale, M.; Małafiejski, M., On the deficiency of bipartite graphs, Discrete Appl. Math., 94, 193-203 (1999) · Zbl 0933.05054
[4] Giaro, K.; Kubale, M.; Małafiejski, M., Consecutive colorings of the edges of general graphs, Discrete Math., 236, 131-143 (2001) · Zbl 1007.05045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.