Marek Kubale

How to contact me:

I am a Professor at

Gdansk University of Technology , ETI Faculty, Department of Algorithms and System Modeling
ul. Narutowicza 11/12, 80-233 Gdańsk, POLAND
Phone: +48 58 347 1818  Fax: +48 58 347 1766
Place: building A of ETI Faculty, room 251

About myself


ul. Ujeścisko 18A m.4, 80-130 Gdańsk



1969 - M.S.E.E.


1975 - Ph.D.


1989 - D.Sc.


1998 - Prof.


2001 - Full Professor

Habilitation Thesis:

Graph Coloring Methods and Their Application in Selected Technological Problems (in Polish)

Posts held:

1975 - 1989

- Assistant Professor, TU Gdańsk


1990 - 1991

- Associate Professor, Head of Department, TU Gdańsk


1991 - 2016  

- Professor, Head of Department, TU Gdańsk


1991 -          

- Professor, University of Gdańsk


1999 - 2005

- Associate Dean for Science, ETI Faculty


Wide experience in design and analysis of computer algorithms. Duties include tuition to students in graph theory, operational research, discrete optimization and computational complexity. Special training in implementation and application of graph coloring algorithms and task scheduling algorithms.

No. of citations:

430 (ISI – Cited Ref. Search)


American Mathematical Society


Institute of Combinatorics and its Applications


Committee of Informatics, Polish Academy of Sciences

Editorial Boards:

Networks (USA) (up to 2000)




Decision Making in Manufacturing and Services (Poland)



Theses supervised:


Janusz Cielątkowski (1996): Modeling and Implementation of Algorithm for Finding Connections in Time Dependant Transportation Networks (in Polish).


Konrad Piwakowski (1996): Application of Algorithmic Methods in Finding Lower and Upper bounds for Ramsey Numbers (in Polish).


Krzysztof Manuszewski (1998): Algorithmically Hard-to-Color Graphs (in Polish).


Włodzimierz Głazek (1999): Algorithms for Scheduling Divisible Tasks on Parallel Machines.


Krzysztof Giaro (1999): Scheduling of Tasks without Two-Sided Waiting Periods on Dedicated Processors (in Polish).


Piotr Borowiecki (2000): On-Line Algorithms for Graph Coloring (in Polish).


Robert Janczewski (2001): T-coloring of Graphs and  its Applications (in Polish).


Michał Małafiejski (2002): Scheduling of Multiprocessor Tasks to Minimize Mean Flow Time (in Polish).


Dariusz Szyfelbein (2003): Methods of Local and Global Search of Solution Space for the Timetabling Problem (in Polish).


Paweł Żyliński (2004): Cooperative Guards Problem - Combinatorial Bounds and Complexity.


Adam Nadolski (2005): Chromatic Task Scheduling in Cyclic Production Systems (in Polish).


Hanna Furmańczyk (2005): Equitable and Cardinality Restricted Graph Coloring (in Polish).


Tomasz Dzido (2006): Ramsey Numbers for Various Classes of Graphs  (in Polish).


Łukasz Kuszner (2006): Distributed Graph Coloring (in Polish).


Dariusz Dereniowski (2006): Parallel Scheduling by Graph Ranking.


Paweł Obszarski (2009): Dedicated Scheduling of UET Tasks in Hypergraph Model (in Polish).


Jacek Dąbrowski (2009): Clonal Selection in Discrete Optimization.


Robert Fidytek (2010): Two and Three-color Ramsey Numbers for Paths and Cycles (in Polish).


Krzysztof Ocetkiewicz (2011): Time-Dependent Task Scheduling (in Polish).


Krzysztof Turowski (2015): Analysis of Algorithmic Properties of Backbone Coloring Problems (in Polish).


Anna Małafiejska (2016): Incidence Coloring of Graphs (in Polish).



M. Kubale, Introduction to Computational Complexity and Algorithmic Graph Coloring, Wydawnictwo GTN, Gdańsk 1998.


M. Kubale, Łagodne wprowadzenie do analizy algorytmów (in Polish), Wydawnictwo PG, Gdańsk 1999, 2002, 2004, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2016, 2017.


M. Kubale  et al.: Optymalizacja dyskretna. Modele i metody kolorowania grafów (in Polish), Wydawnictwa Naukowo-Techniczne, Warszawa 2002.


M. Kubale  et al.: Graph Colorings, American Mathematical Society, Providence, Rhode Island, 2004.


Selected Recent Articles: 

K. Giaro, M.Kubale, A note on polynomial al algorithm for cost coloring of bipartite graphs with ∆≤4, Discussiones Mathematicae Graph Theory, (2019), in press.

  T. Pikies, M. Kubale, Better polynomial algorithms for scheduling unit-length jobs with
bipartite incompatibility graphs on uniform machines
, Bulletin of the Polish Academy of Sciences, 67 (2019), 31-36.
  H. Furmańczyk, M. Kubale, Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs, Discrete Applied Mathematics, 237 (2018), 116-122. [MR3763304].
  H. Furmańczyk, M. Kubale, Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines, Discrete Applied Mathematics, 234 (2018), 210-217. [MR3736922].
  M. Duraj, P. Kopeć, M. Kubale, T. Pikies, Scheduling of Identical Jobs with Bipartite Incompatibility Graphs on Uniform Machines. Computational Experiments, Decision Making in Manufacturing and Services, AGH, 11 (2017), 53-61. [MR3733168] .
  H. Furmańczyk, M. Kubale, Scheduling of unit-length jobs with bipartite incompatibility graphs
on four uniform machines,
Bulletin of the Polish Academy of Sciences – Technical Sciences,  65 (2017),  29 - 34.
  H. Furmańczyk, M. Kubale, V. V. Mkrtchyan, Equitable colorings of corona multiproduct of graphs, Disc. Math. Graph Theory, 37 (2017), 1079-1094. [MR3684127].
  H. Furmańczyk, A. Jastrzębski, M. Kubale, Equitable coloring of graphs. Recent theoretical
results and new practical algorithms
, Archives Control Sciences, 26 (2016), 281-295. [MR3744255].

H. Furmańczyk, M. Kubale, St. Radziszowski, On bipartization of cubic graphs by removal of an independent set, Discrete Applied Mathematics, 209 (2016), 15–121. [MR3510435].


H. Furmańczyk, M. Kubale, Equitable coloring of corona products of cubic graphs is harder than ordinary coloring, Ars Mathematica Contemporanea, 10 (2016), 333-347. [MR3529295].


M. Jurkiewicz, M. Kubale, K. Ocetkiewicz, On the independence number of some strong products of cycle-PowersFoundations of Computing and Decision Sciences, The Journal of Poznan University of Technology, 40 (2015), 133–141. [MR3410566].


P. Obszarski, A. Jastrzębski, M. Kubale, Towards the boundary between easy and hard control problems in multicast Clos networks, Bulletin of the Polish Academy of Sciences – Technical Sciences, 63 (2015), 739-744.


H. Furmańczyk, M. Kubale, Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling, Archives Control Sciences, 25 (2015), 109-116. [MR34345478].


M. Jurkiewicz, M. Kubale, K. Turowski, Some lower bounds on the Shannon capacity, Journal of Applied Computer Science, 22 (2014), 31-42.


H. Furmańczyk, K. Kaliraj, M. Kubale, J.V. Vivin, Equitable coloring of corona products of graphs, Adv. App. Disc. Math., 11, No. 2, (2013), 103-120. [MR3099949].


M. Kubale, Modele i metody kolorowania grafów.  Część II. Przegląd Elektrotechniczny 88 (2012), 51-55.


M. Kubale, Million Dollar Algorithm? Academia 29 (2011), 32-35.


M. Jurkiewicz, M. Kubale, A note on Shannon capacity for invariant and evolving channels, Journal of Applied Computer Science 19 (2011), 19-29.


M. Kubale, Modele i metody kolorowania grafów.  Część I. Przegląd Elektrotechniczny 86 (2010), 115-117.


M. Kubale, K. Ocetkiewicz, A new optimal algorithm for a time-dependent scheduling problemControl and Cybernetics 38 (2009), 713-721. [MR2650362J].


K. Giaro, M. Kubale, Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs, Disc. Math. Graph Theory 29 (2009), 361-376. [MR#11i: 05073].


K. Giaro, M. Kubale, P. Obszarski, A graph coloring approach to scheduling multiprocessor task on dedicated machines with availability constrains, Disc. Appl. Math. 157 (2009), 3625-3630. [MR#10k: 05299].


D. Dereniowski, M. Kubale, Program  verification  strategy  and  edge  ranking  of  graphs, Polish Journal of Environmental Studies 17, 2A (2008), 124-128.


T. Dzido, M. Kubale, K. Piwakowski, On some Ramsey and Turán-type numbers for paths and cycles, Electr. J. of Comb. 13 (2006), #55. [MR#07d: 05108].

  H. Furmańczyk, K. Giaro, M. Kubale, Equitable 4-coloring of cacti and edge-cacti in polynomial time, Int. J. Pure Appl Mathematics 27 (2006), 377-389. [MR2219570]
  K. Giaro, M. Kubale, Chromatic scheduling of 1- and 2-processor UET tasks on dedicated machines with availability constraints, LNCS 3911 (2006), 855-862.
  D.Dereniowski, M.Kubale, Parallel query processing and edge ranking of graphsLNCS 3911 (2006), 463-469.
  D.Dereniowski, M.Kubale, Efficient parallel query processing by graph ranking, Fundamenta Informaticae 69 (2006), 273-285. [MR#08f: 68024]
  M. Małafiejski, K. Giaro, R. Janczewski, M. Kubale, Sum coloring of bipartite graphs with bounded degree, Algorithmica 40 (2004), 235-244.
  D. Dereniowski, M. Kubale, Cholesky factorization of matrices in parallel and ranking of graphs, LNCS  3019 (2004), 985-992 .
  Giaro K., Kubale M., Piwakowski K.: Complexity results on open shop scheduling to minimize total cost of operations, Int. J. Comp. Sys. Sign. 3 (2002),  84-91.
  K. Giaro, R. Janczewski, M. Kubale, M. Małafiejski, A 27/26-approximation algorithm for the chromatic sum coloring of bipartite graphs, LNCS 2462 (2002), 135-145. [MR2091822]
  K. Giaro, M. Kubale, M. Małafiejski, K. Piwakowski, Dedicated scheduling of biprocessor tasks to minimize mean flow time, LNCS 2328 (2002), 87-96.
  M. Kubale, K. Manuszewski, K. Giaro, On the smallest hard to color sequentially graph, Cong. Numer. 150 (2001), 155-160. [MR#02m: 05088]
  K. Giaro, M. Kubale, M. Małafiejski, Consecutive colorings of the edges of general graphs, Disc. Math. 236 (2001), 131-143. [MR#02a: 05100]
  R. Janczewski, M. Kubale, K. Manuszewski, K. Piwakowski, The smallest hard-to-color graph for algorithm DSATUR, Disc. Math. 236 (2001), 151-165. [MR#02a: 05231]
  K. Giaro, M. Kubale, Edge-chromatic sum of trees and bounded cyclicity graphs, Inf. Prosess. Lett. 75 (2000), 65-69. [MR#01g: 68041]



 Bridge, tennis.