On one-sided interval edge colorings of biregular bipartite graphs

Rafayel Ruben Kamalian

Abstract


A proper edge \(t\)-coloring of a graph $G$ is a coloring of edges of
\(G\) with colors \(1,2,\ldots,t\) such that all colors are used, and no
two adjacent edges receive the same color. The set of colors of
edges incident with a vertex \(x\) is called a spectrum of \(x\). Any
nonempty subset of consecutive integers is called an interval. A
proper edge \(t\)-coloring of a graph \(G\) is interval in the vertex
$x$ if the spectrum of \(x\) is an interval. A proper edge
\(t\)-coloring \(\varphi\) of a graph \(G\) is interval on a subset \(R_0\)
of vertices of \(G\), if for any \(x\in R_0\), \(\varphi\) is interval in
\(x\). A subset \(R\) of vertices of \(G\) has an \(i\)-property if there is
a proper edge \(t\)-coloring of \(G\) which is interval on \(R\). If \(G\)
is a graph, and a subset \(R\) of its vertices has an \(i\)-property,
then the minimum value of \(t\) for which there is a proper edge
\(t\)-coloring of \(G\) interval on \(R\) is denoted by \(w_R(G)\). We estimate the value of this parameter for biregular bipartite graphs in the case when \(R\) is one of the sides of a bipartition of the graph.

Keywords


proper edge coloring, interval edge coloring, interval

Full Text:

PDF

References


A.S. Asratian, Investigation of some mathematical model of Scheduling Theory,

Doctoral Dissertation, Moscow University, 1980 (in Russian).

A.S. Asratian, C.J. Casselgren, A sufficient condition for interval edge colorings of

(4, 3)-biregular bipartite graphs, Research report LiTH-MAT-R-2006-07, Linköping

University, 2006.

A.S. Asratian, C.J. Casselgren, Some results on interval edge colorings of (, )-

biregular bipartite graphs, Research report LiTH-MAT-R-2006-09, Linköping University,

A.S. Asratian, C.J. Casselgren, On interval edge colorings of (, )-biregular

bipartite graphs, Discrete Math 307 (2007), pp.1951-1956.

A.S. Asratian, C.J. Casselgren, J. Vandenbussche, D.B. West, Proper path-factors

and interval edge-coloring of (3, 4)-biregular bigraphs, J. of Graph Theory 61 (2009),

pp.88-97.

A.S. Asratian, T.M.J. Denley, R. Haggkvist, Bipartite graphs and their applications,

Cambridge Tracts in Mathematics, 131, Cambridge University Press, 1998.

A.S. Asratian, R.R. Kamalian, Interval colorings of edges of a multigraph, Appl.

Math. 5 (1987), Yerevan State University, pp.25-34 (in Russian).

A.S. Asratian, R.R. Kamalian, Investigation of interval edge-colorings of graphs,

Journal of Combinatorial Theory. Series B 62 (1994), N.1, pp.34-43.

M.A. Axenovich, On interval colorings of planar graphs, Congr. Numer. 159 (2002),

pp.77-94.

D.P. Geller and A.J.W. Hilton, How to color the lines of a bigraph, Networks,

(1974), pp.281-282.

K. Giaro, Compact task scheduling on dedicated processors with no waiting periods,

PhD thesis, Technical University of Gdansk, EIT faculty, Gdansk, 1999 (in Polish).

K. Giaro, The complexity of consecutive -coloring of bipartite graphs: 4 is easy,

is hard, Ars Combin. 47(1997), pp.287-298.

K. Giaro, M. Kubale and M. Malafiejski, On the deficiency of bipartite graphs,

Discrete Appl. Math. 94 (1999), pp.193-203.

H.M. Hansen, Scheduling with minimum waiting periods, Master’s Thesis, Odense

University, Odense, Denmark, 1992 (in Danish).

D. Hanson, C.O.M. Loten, B. Toft, On interval colorings of bi-regular bipartite

graphs, Ars Combin. 50(1998), pp.23-32.

T.R. Jensen, B. Toft, Graph Coloring Problems, Wiley Interscience Series in

Discrete Mathematics and Optimization, 1995.

R.R. Kamalian, Interval Edge Colorings of Graphs, Doctoral dissertation, the

Institute of Mathematics of the Siberian Branch of the Academy of Sciences of

USSR, Novosibirsk, 1990 (in Russian).

R.R. Kamalian, On one-sided interval colorings of bipartite graphs, the Herald of

the RAU, N.2, Yerevan, 2010, pp.3-11 (in Russian).

R.R. Kamalian, Interval colorings of complete bipartite graphs and trees, Preprint

of the Computing Centre of the Academy of Sciences of Armenia, Yerevan, 1989

(in Russian).

M. Kubale, Graph Colorings, American Mathematical Society, 2004.

P.A. Petrosyan, Interval edge-colorings of complete graphs and n-dimensional

cubes, Discrete Math. 310 (2010), pp.1580-1587.

P.A. Petrosyan, On interval edge-colorings of multigraphs, The Herald of the RAU,

N.1, Yerevan, 2011, pp.12-21 (in Russian).

P.A. Petrosyan, H.H. Khachatrian, Interval non-edge-colorable bipartite graphs

and multigraphs, J. of Graph Theory 76 (2014), pp.200-216.

A.V. Pyatkin, Interval coloring of (3, 4)-biregular bipartite graphs having large

cubic subgraphs, J. of Graph Theory 47 (2004), pp.122-128.

S.V. Sevast’janov, Interval colorability of the edges of a bipartite graph, Metody

Diskret. Analiza 50(1990), pp.61-72 (in Russian).

V.G. Vizing, The chromatic index of a multigraph, Kibernetika 3 (1965), pp.29-39.

D.B. West, Introduction to Graph Theory, Prentice-Hall, New Jersey, 1996.

F. Yang, X. Li, Interval coloring of (3, 4)-biregular bigraphs having two (2, 3)-

biregular bipartite subgraphs, Appl. Math. Letters 24(2011), pp.1574-1577.

Y. Zhao and J.G. Chang, Consecutive Edge-Colorings of Generalized -Graphs, J.

Akiyama et al. (Eds.): CGGA 2010, LNCS 7033, 2011, pp.214-225.


Refbacks

  • There are currently no refbacks.