9 papers
Backbone coloring for graphs with degree 4
Krzysztof Michalik, Krzysztof Turowski
The -backbone coloring of the graph with backbone is a graph-coloring problem in which we are given a graph and a subgraph , and we want to assign colors to verti…
Edge coloring of products of signed graphs
Robert Janczewski, Krzysztof Turowski, Bartłomiej Wróblewski
In 2020, Behr defined the problem of edge coloring of signed graphs and showed that every signed graph can be colored using exactly or colors, where $Δ(G…
On the concentration of the maximum degree in the duplication-divergence models
Alan Frieze, Krzysztof Turowski, Wojciech Szpankowski
We present a rigorous and precise analysis of the maximum degree and the average degree in a dynamic duplication-divergence graph model introduced by Solé, Pastor-Satorras et al. i…
The Game Chromatic Number of Complete Multipartite Graphs
Paweł Obszarski, Krzysztof Turowski, Hubert Zięba
In this paper we investigate the game chromatic number for complete multipartite graphs. Our results consist of two findings: (1) building on Dunn's strategies for equal-sized part…
Approximation algorithms for job scheduling with block-type conflict graphs
Hanna Furmańczyk, Tytus Pikies, Inka Sokołowska +1
The problem of scheduling jobs on parallel machines (identical, uniform, or unrelated), under incompatibility relation modeled as a block graph, under the makespan optimality crite…
Edge coloring of graphs of signed class 1 and 2
Robert Janczewski, Krzysztof Turowski, Bartłomiej Wróblewski
Recently, Behr introduced a notion of the chromatic index of signed graphs and proved that for every signed graph , it holds that \[ Δ(G)\leqχ'(G\text{, }σ)\leqΔ(G)+1\text…
On λ-backbone coloring of cliques with tree backbones in linear time
Krzysztof Michalik, Krzysztof Turowski
A -backbone coloring of a graph with its subgraph (also called a backbone) is a function ensuring that is a proper colorin…
Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines
Tytus Pikies, Krzysztof Turowski, Marek Kubale
In this paper we consider the problem of scheduling on parallel machines with a presence of incompatibilities between jobs. The incompatibility relation can be modeled as a complet…
Temporal Ordered Clustering in Dynamic Networks: Unsupervised and Semi-supervised Learning Algorithms
Krzysztof Turowski, Jithin K. Sreedharan, Wojciech Szpankowski
In temporal ordered clustering, given a single snapshot of a dynamic network in which nodes arrive at distinct time instants, we aim at partitioning its nodes into ordered clus…