Interval edge coloring

Updated on Dec 11, 2023

Edit

Comment

Interval edge coloring is a type of edge coloring in which edges are colored such that they form a set of intervals and each color in the interval set is at least used once to color the edges of the graph.It is to be noted that at each vertex in the graph the colors used form a consecutive set of natural numbers.

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". 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 doesnot 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.

Astrain and Kamalian in their paper 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.

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. 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 atmost 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.In Asratian and Kamalian proved if G is interval color-able then χ'(G)=∆(G).

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. Axenovich proved that all outerplanar triangulations with more than three vertices and without separating triangles are interval colorable. 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

Complete graph is interval colorable if and only if the number of its vertices is even.

The complete bipartite graph K_m,n has an interval t-coloring if and only if m+n−gcd(m,n) ≤ t ≤ m+n−1,where gcd(m,n) is the greatest common divisor of m and n.

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 ≤ n ( n + 1 ) 2 , then the n-dimensional cube Qn has an interval t-coloring.

Interval edge coloring of bipatite 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

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

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 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.

Interval edge coloring of Grid graphs

The cartesian product of two paths P_m and P_n is said to be the grid graph and is denoted by G_m,n.

Example

Interval edge coloring of Grid graph G_4,5.That is,

The grid graph G_4,5 satisfies the definition of interval edge coloring.Therefore, χ i e ( G 4 , 5 ) =4.

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 χ e i e ( 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.

References

Interval edge coloring Wikipedia

(Text) CC BY-SA

Contents