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 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. 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 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). 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. If n=p2q, where p is odd, q is nonnegative, and 2n−1≤t≤4n−2−p−q, then the complete graph K2n has an interval t-coloring. If F is a set of at least n edges incident to one vertex v of the complete graph K2n+1, then K2n+1−F has an interval coloring. If F is a maximum matching of the complete graph K2n+1 with n≥2, then K2n+1−F has no interval coloring. If n ≤ t ≤ n ( n + 1 ) 2 {\displaystyle {\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 Km,n is interval colorable, and (1) w (Km,n) = m + n − gcd(m, n), (2) W (Km,n) = m + n − 1, (3) if w (Km,n) ≤ t ≤ W (Km,n), then Km,n has an interval t-coloring.
If G is a bipartite graph, then χ′(G) = ∆(G). If G ∈ N, then G[Km,n] ∈ N for any m, n ∈ N. Moreover, for any m, n ∈ N,we have w (G[Km,n]) ≤ (w(G) + 1)(m + n) − 1 and W (G[Km,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=G1eG2 where G1 and G2 have interval colorings in which e has an external label. Then G has an interval coloring. 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(e)=0. Consider an interval coloring c1 ofG1 where e gets the largest label among edges incident to x and y.Say,c2(e)=i. Then we construct an interval coloring c of G as c(e')=c1(e') if (e')∈E(G1) or c(e')=c2(e')-i if (e')∈ E(G1).
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=H1,-----Hm be decomposition with connecting edges e1,----,em-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.
… excerpt ends here. Continue reading the full article.
