Interval edge coloring


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

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.
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 ∈ 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 GN, the least and the greatest values of t for which G has an interval t-colouring are denoted by w and W, 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 is called a spectrum of. 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= has an interval t-coloring, then t ≤ |V|−1. Asratyan and Kamalian proved if G is interval color-able then χ'=∆.
Petrosyan investigated interval colorings of complete graphs and n-dimensional cubes and showed if n ≤ t ≤ n/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=∆ and G has an interval t-coloring for every t, w ≤ t ≤ W.

Interval edge coloring of complete graph

w = m + n − gcd,
W = m + n − 1,
if w ≤ t ≤ W,
then Km,n has an interval t-coloring.
w ≤ − 1 and W ≥ − 1.
Interval edge-colorings of outerplanar graphs were investigated by Giaro and Kubale and proved all the outer planar bipartite graphs are interval colorable.
Proof: Let c1 be an interval coloring of 'G1' such that e=xy gets the smallest label among edges incident to x and y.Take c1=0. Consider an interval interval coloring c1 ofG1 where e gets the largest label among edges incident to x and y.Say,c2=i. Then we construct an interval coloring c of G as c=c1 if '∈E or c=c2-i if '∈ E.
A bipartite graph is -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 ∆ ≤ 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 E1,E2,...,Ek such that Ei is an independent set and the condition -1 ≤ Ei ≤ Ej ≤ 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.

Applications

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