HFHanna Furmańczyk

Hanna Furmańczyk

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Hanna Furmańczyk has a total of 30 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Packing coloring of graphs with long paths

    by Hanna Furmańczyk, Didem Gözüpek, Sibel Özkan

    The packing coloring problem has diverse applications, including frequency assignment in wireless networks, resource distribution and facility location in smart cities and post-disaster management, as well as in biological diversity. Formally, the packing coloring of a graph is a vertex coloring in which any two vertices assigned color $i$ are at a distance of at least $i+1$, and the smallest number of colors admitting such a coloring is called the packing chromatic number. Goddard et al.~\cite{goddard2008broadcast} showed that the packing chromatic numbers of paths and cycles are at most 3 and 4, respectively. In this paper, we introduce \emph{path-aligned graph products}, a natural extension of paths with unbounded diameter. We extend the result of~\cite{goddard2008broadcast} by proving that the packing chromatic number remains bounded by a constant for several families of path-aligned cycle and path-aligned complete products. We then investigate the packing chromatic number of caterpillars, another class of graphs characterized by long induced paths. Sloper~\cite{sloper} proved that the packing chromatic number of caterpillars is at most 7; here, we provide a complete structural characterization of caterpillars with packing chromatic number at most 3. Finally, several open research questions are posed.

  • Open Access

    Adjacent vertex distinguishing total coloring of corona product of graphs

    by Hanna Furmańczyk, Rita Zuazua

    AMC is a journal published by University of Primorska.


  • A new approach to b-coloring of regular graphs

    by Magda Dettlaff, Hanna Furmańczyk, Iztok Peterin, Adriana Roux, Radosław Ziemann


  • Open Access

    Equitable colorings of l-corona products of cubic graphs

    by Hanna Furmańczyk, Marek Kubale

    A graph G is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest integer k for which such a coloring exists is known as the equitable chromatic number of G and it is denoted by x=( G). In this paper the problem of determining the value of equitable chromatic number for multicoronas of cubic graphs G◦ lH is studied. The problem of ordinary coloring of multicoronas of cubic graphs is solvable in polynomial time. The complexity of equitable coloring problem is an open question for these graphs. We provide some polynomially solvable cases of cubical multicoronas and give simple linear time algorithms for equitable coloring of such graphs which use at most x=( G◦ lH) + 1 colors in the remaining cases.

  • Approximation algorithms for job scheduling with block-type conflict graphs

    by Hanna Furmańczyk, Tytus Pikies, Inka Sokołowska, Krzysztof Turowski


  • Open Access

    Approximation algorithms for job scheduling with block-type conflict graphs

    by Hanna Furmańczyk, Tytus Pikies, Inka Sokołowska, Krzysztof Turowski

    The problem of scheduling jobs on parallel machines (identical, uniform, or unrelated), under incompatibility relation modeled as a block graph, under the makespan optimality criterion, is considered in this paper. No two jobs that are in the relation (equivalently in the same block) may be scheduled on the same machine in this model. The presented model stems from a well-established line of research combining scheduling theory with methods relevant to graph coloring. Recently, cluster graphs and their extensions like block graphs were given additional attention. We complement hardness results provided by other researchers for block graphs by providing approximation algorithms. In particular, we provide a $2$-approximation algorithm for $P|G = block\ graph|C_{max}$ and a PTAS for the case when the jobs are unit time in addition. In the case of uniform machines, we analyze two cases. The first one is when the number of blocks is bounded, i.e. $Q|G = k-block\ graph|C_{max}$. For this case, we provide a PTAS, improving upon results presented by D. Page and R. Solis-Oba. The improvement is two-fold: we allow richer graph structure, and we allow the number of machine speeds to be part of the input. Due to strong NP-hardness of $Q|G = 2-clique\ graph|C_{max}$, the result establishes the approximation status of $Q|G = k-block\ graph|C_{max}$. The PTAS might be of independent interest because the problem is tightly related to the NUMERICAL k-DIMENSIONAL MATCHING WITH TARGET SUMS problem. The second case that we analyze is when the number of blocks is arbitrary, but the number of cut-vertices is bounded and jobs are of unit time. In this case, we present an exact algorithm. In addition, we present an FPTAS for graphs with bounded treewidth and a bounded number of unrelated machines.

  • Open Access

    Block graphs - some general results and their equitable colorings

    by Hanna Furmańczyk, Vahan Mkrtchyan

    In this paper, we consider some general properties of block graphs as well as the equitable coloring problem in this class of graphs. In the first part we establish the relation between two structural parameters for general block graphs. We also give complete characterization of block graphs with given value of parameter $α_{\min}$. In the next part of the paper we confirm the hypothesis for some subclass of GLS block graphs in which the problem of EQUITABLE COLORING is unlikely to be polynomial time solvable. We give also an equitable $(n+2)$-algorithm for all GLS block graphs. As a by product we prove that the equitable chromatic spectrum for the subclass of GLS block graphs is gap-free.

  • Open Access

    A new approach to b-coloring of regular graphs

    by Magda Dettlaff, Hanna Furmańczyk, Iztok Peterin, Riana Roux, Radosław Ziemann

    Let $G$ be a graph and c a proper k-coloring of G, i.e. any two adjacent vertices u and v have different colors c(u) and c(v). A proper k-coloring is a b-coloring if there exists a vertex in every color class that contains all the colors in its closed neighborhood. The maximum number of colors k admitting b-coloring of G is the b-chromatic number. We present two separate approaches to the conjecture posed by Blidia et. al that the b-chromatic number equals to d+1 for every d-regular graph of girth at least five except the Petersen graph.

  • Open Access

    Gap one bounds for the equitable chromatic number of block graphs

    by Janusz Dybizbański, Hanna Furmańczyk, Vahan Mkrtchyan


  • Open Access

    Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs

    by Hanna Furmańczyk, Vahan Mkrtchyan

    An equitable coloring of a graph $G=(V,E)$ is a (proper) vertex-coloring of $G$, such that the sizes of any two color classes differ by at most one. In this paper, we consider the equitable coloring problem in block graphs. Recall that the latter are graphs in which each 2-connected component is a complete graph. The problem remains hard in the class of block graphs. In this paper, we present some graph theoretic results relating various parameters. Then we use them in order to trace some algorithmic implications, mainly dealing with the fixed-parameter tractability of the problem.