4 papers · 1 filter
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…
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…