Interval edge coloring

Last updated August 19, 2023

In graph theory, interval edge coloring is a type of edge coloring in which edges are labeled by the integers in some interval, every integer in the interval is used by at least one edge, and at each vertex the labels that appear on incident edges form a consecutive set of distinct numbers.

History
Definition
A few results
Interval edge coloring of complete graph[2]
Interval edge coloring of bipartite graphs
Interval edge coloring of Planar graphs[4]
Interval edge coloring of biregular bipartite graphs with small vertex degrees
Equitable K-interval edge coloring
Applications
Conjectures
References
See also

History

The concept of consecutive edge-coloring was introduced with the terminology 'interval edge coloring' by Asratian and Kamalian in 1987 in their paper "Interval colorings of edges of a multigraph".^[1] Since interval edge coloring of graphs was introduced mathematicians have been investigating the existence of interval edge colorable graphs as not all graphs allow interval edge coloring. A simple family of graphs that allows interval edge coloring is complete graph of even order and a counter example of family of graphs includes complete graphs of odd order. The smallest graph that does not allow interval colorability. There are even graphs discovered with 28 vertices and maximum degree 21 that is not interval colorable by Sevast’janov though the interval colorability of graphs with maximum degree lying between four and twelve is still unknown.

Asratyan & Kamalyan (1987) proved that if a graph is interval colorable then the edge chromatic number is less than or equal to one less than its number of vertices and also noted that if G is r-regular, then G has an interval coloring if and only if G has a proper r-edge-coloring.^[1]

Interval edge coloring is investigated in regular graphs.bipartite graphs which are regular and not regular, planar graphs, among the other extensions that has been initiated in interval edge coloring.

Definition

Let G be a simple interval graph. An edge-colouring of a graph G with colours 1, 2, . . . , t is called an ""interval t-colouring"" if for each i ∈ {1, 2, . . . , t} there is at least one edge of G coloured by i and the colours of edges incident to any vertex of G are distinct and form an interval of integers.^[2] Alternatively an interval edge coloring defined as: An edge-colouring of a graph G with colours 1. . . t is an 'interval t-colouring' if all colours are used, and the colours of edges incident to each vertex of G are distinct and form an interval of integers. A graph G is "interval colourable" if G has an interval t-colouring for some positive integer t. Let N be the set of all interval colourable graphs. For a graph G ∈ N, the least and the greatest values of t for which G has an interval t-colouring are denoted by w(G) and W(G), respectively. An interval edge coloring of a graph is said to be equitable interval edge coloring if any two color classes of a graph differ by at most one.

The set of colors of edges incident with a vertex (x) is called a spectrum of (x). We say that a subset R of vertices of G has an i-property if there is a proper edge t-coloring of G which is interval over R.

A few results

If a triangle-free graph G=(V,E) has an interval t-coloring, then t ≤ |V|−1. Asratyan and Kamalian proved if G is interval color-able then χ'(G)=∆(G).^[1]^[3]

Petrosyan investigated interval colorings of complete graphs and n-dimensional cubes and showed if n ≤ t ≤ n(n+1)/2,then the n-dimensional cube Qn has an interval t-coloring.^[2] Axenovich proved that all outerplanar triangulations with more than three vertices and without separating triangles are interval colorable.^[4] If G is regular graph w(G)=∆(G) and G has an interval t-coloring for every t, w(G) ≤ t ≤ W(G).

Interval edge coloring of complete graph^[2]

Complete graph is interval colorable if and only if the number of its vertices is even.
If n=_p2^q, where p is odd, q is nonnegative, and 2n−1≤t≤4n−2−p−q, then the complete graph K_2n has an interval t-coloring.
If F is a set of at least n edges incident to one vertex v of the complete graph K_2n+1, then K_2n+1−F has an interval coloring.
If F is a maximum matching of the complete graph K_2n+1 with n≥2, then K_2n+1−F has no interval coloring.
If n ≤ t ≤ ${\frac {n(n+1)}{2}}$ , then the n-dimensional cube Qn has an interval t-coloring.

Interval edge coloring of bipartite graphs

For any m, n ∈ N, the complete bipartite graph K_m,n is interval colorable, and

(1) w (K_m,n) = m + n − gcd(m, n),

(2) W (K_m,n) = m + n − 1,

(3) if w (K_m,n) ≤ t ≤ W (K_m,n), then K_m,n has an interval t-coloring.

If G is a bipartite graph, then χ′(G) = ∆(G).
If G ∈ N, then G[K_m,n] ∈ N for any m, n ∈ N. Moreover, for any m, n ∈ N,we have

w (G[K_m,n]) ≤ (w(G) + 1)(m + n) − 1 and W (G[K_m,n]) ≥ (W(G) + 1)(m + n) − 1.

If G is a connected bipartite graph and G ∈ N, then W(G) ≤ diam(G) (∆(G) − 1) + 1.

Interval edge coloring of Planar graphs^[4]

Interval edge-colorings of outerplanar graphs were investigated by Giaro and Kubale and proved all the outer planar bipartite graphs are interval colorable.^[5]

IfG=G₁eG₂ where G₁ and G₂ have interval colorings in which e has an external label. Then G has an interval coloring.

Proof: Let c₁ be an interval coloring of 'G₁' such that e=xy gets the smallest label among edges incident to x and y.Take c₁(e)=0. Consider an interval coloring c₁ ofG₁ where e gets the largest label among edges incident to x and y.Say,c₂(e)=i. Then we construct an interval coloring c of G as c(e')=c₁(e') if (e')∈E(G₁) or c(e')=c₂(e')-i if (e')∈ E(G₁).

If G is an outerplanar graph of order at least 4 without separating triangles then it has an interval coloring.
Let G be a graph obtained by deleting some dividing edges under some interval coloring of a graph H. Then G is an interval colorable.
let H be an outerplanar triangulation with no separate triangles and let H=H₁,-----H_m be decomposition with connecting edges e₁,----,e_m-1.If G is obtained from H by deleting some connecting edges, then G has an interval coloring.
For any planar interval colorable graph G on n vertices t(G)≤(11/6)n.

Interval edge coloring of biregular bipartite graphs with small vertex degrees

A bipartite graph is (a, b)-biregular if everyvertex in one part has degree a and every vertex in the other part has degree b. It has been conjectured that all such graphs have interval colorings. Hansen proved that every bipartite graph G with ∆(G) ≤ 3 is interval colorable.

Equitable K-interval edge coloring

A k-interval edge coloring of a graph is said to be equitable k-interval edge coloring if its edge set E is partitioned into K subsets E₁,E₂,...,E_k such that E_i is an independent set and the condition -1 ≤ E_i ≤ E_j ≤ 1 holds for all 1 ≤i ≤k,1 ≤j ≤k. The smallest integer k for which G is equitable interval edge coloring is known as the equitable chromatic number of interval edge coloring of G and is denoted by $\chi _{eie}(G)$ .

Applications

Interval edge coloring has wide applications in various fields of science and scheduling.

One of the basic applications of interval edge coloring is the scheduling of the timetable for classes without clashes, in this application the class hours become the vertices and they share an edge if both share a time interval.The number of colors needed to color the edges are the number of classes needed to conduct classes without clashes. This is used in all instances where two or more events need to be organized avoiding clashes.
A similar application is found in the time scheduling of the run time of the processors.E.g. scheduling file transfers in a distributed network or scheduling diagnostic tests in a multicomputer system as well as scheduling tasks in an open shop system.Various algorithms are being developed for this purpose.
Interval edge colorability of complete graphs helps in scheduling 2n plays in a tournament such that each team plays with each other.
Many other applications are arising with the study of interval edge colorability of planar graphs and bipartite graphs.

Conjectures

For any m,n∈N, K1,m,n ∈ N if and only if gcd(m+1, n+1) = 1.
If G is a planar graph on n vertices then the maximal number of colors used in an interval coloring of G is at most (3/2)n.
An outerplanar graph obtained from an outerplanar triangulation with no separating triangles by deleting internal edges is interval colorable.

Related Research Articles

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most $k$ different colors, for a given value of $k$ , or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

In graph theory, a branch of mathematics, list coloring is a type of graph coloring where each vertex can be restricted to a list of allowed colors. It was first studied in the 1970s in independent papers by Vizing and by Erdős, Rubin, and Taylor.

In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent edges, no adjacent vertices and no edge and either endvertex are assigned the same color. The total chromatic number χ″(G) of a graph G is the fewest colors needed in any total coloring of G.

In graph theory, a complete coloring is a vertex coloring in which every pair of colors appears on at least one pair of adjacent vertices. Equivalently, a complete coloring is minimal in the sense that it cannot be transformed into a proper coloring with fewer colors by merging pairs of color classes. The achromatic number $ψ(G)$ of a graph $G$ is the maximum number of colors possible in any complete coloring of $G$ .

In graph theory, the Hadwiger conjecture states that if $is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.$

In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings in a book, a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the spine, and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number.

In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree $Δ$ of the graph. At least $Δ$ colors are always necessary, so the undirected graphs may be partitioned into two classes: "class one" graphs for which $Δ$ colors suffice, and "class two" graphs for which $Δ + 1$ colors are necessary. A more general version of Vizing's theorem states that every undirected multigraph without loops can be colored with at most $Δ+µ$ colors, where $µ$ is the multiplicity of the multigraph. The theorem is named for Vadim G. Vizing who published it in 1964.

<span class="mw-page-title-main">Kőnig's theorem (graph theory)</span> Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (1931), describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

In graph theory, a mathematical discipline, coloring refers to an assignment of colours or labels to vertices, edges and faces of a graph. Defective coloring is a variant of proper vertex coloring. In a proper vertex coloring, the vertices are coloured such that no adjacent vertices have the same colour. In defective coloring, on the other hand, vertices are allowed to have neighbours of the same colour to a certain extent.

In the mathematical study of graph theory, a pancyclic graph is a directed graph or undirected graph that contains cycles of all possible lengths from three up to the number of vertices in the graph. Pancyclic graphs are a generalization of Hamiltonian graphs, graphs which have a cycle of the maximum possible length.

In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge. If a 1-planar graph, one of the most natural generalizations of planar graphs, is drawn that way, the drawing is called a 1-plane graph or 1-planar embedding of the graph.

<span class="mw-page-title-main">Adjacent-vertex-distinguishing-total coloring</span> Type of total coloring in graph theory

In graph theory, a total coloring is a coloring on the vertices and edges of a graph such that:

The graph coloring game is a mathematical game related to graph theory. Coloring game problems arose as game-theoretic versions of well-known graph coloring problems. In a coloring game, two players use a given set of colors to construct a coloring of a graph, following specific rules depending on the game we consider. One player tries to successfully complete the coloring of the graph, when the other one tries to prevent him from achieving it.

In graph theory, the act of coloring generally implies the assignment of labels to vertices, edges or faces in a graph. The incidence coloring is a special graph labeling where each incidence of an edge with a vertex is assigned a color under certain constraints.

References

1 2 3 Asratyan, A. S.; Kamalyan, R. R. (1987), "Interval colorings of the edges of a multigraph", in Tonoyan, R. N. (ed.), Прикладная математика. Вып. 5.[Applied mathematics. No. 5] (in Russian), Erevan: Erevan. Univ., pp. 25–34, 130–131, MR 1003403
1 2 3 Petrosyan, P. A. (2010), "Interval edge-colorings of complete graphs and $n$ -dimensional cubes", Discrete Mathematics , 310 (10–11): 1580–1587, doi:10.1016/j.disc.2010.02.001, MR 2601268
↑ Asratian, A. S.; Kamalian, R. R. (1994), "Investigation on interval edge-colorings of graphs", Journal of Combinatorial Theory , Series B, 62 (1): 34–43, doi: 10.1006/jctb.1994.1053 , MR 1290629
1 2 Axenovich, Maria A. (2002), "On interval colorings of planar graphs", Proceedings of the Thirty-Third Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2002), Congressus Numerantium, vol. 159, pp. 77–94, MR 1985168
↑ Giaro, Krzysztof; Kubale, Marek (2004), "Compact scheduling of zero-one time operations in multi-stage systems", Discrete Applied Mathematics , 145 (1): 95–103, doi:10.1016/j.dam.2003.09.010, MR 2108435