Source author record

Hanna Furmańczyk

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

4works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Adjacent Vertex Distinguishing Total Coloring of Corona Product of Graphs

An adjacent vertex distinguishing total $k$ -coloring $f$ of a graph $G$ is a proper total $k$ -coloring of $G$ such that no pair of adjacent vertices has the same color sets, where the color set at a vertex $v$ , $C^G_f(v)$ , is $\{f(v)\} \cup \{f(vu)|u \in V (G), vu \in E(G)\}$ . In 2005 Zhang et al. posted the conjecture (AVDTCC) that every simple graph $G$ has adjacent vertex distinguishing total $(Δ(G)+3)$ -coloring. In this paper we confirm the conjecture for many coronas, in particular for generalized, simple and $l$ -coronas of graphs, not relating the results to particular graph classes.

preprint2020arXiv

Vizing-Goldberg type bounds for the equitable chromatic number of block graphs

An equitable coloring of a graph $G$ is a proper vertex coloring of $G$ such that the sizes of any two color classes differ by at most one. In the paper, we pose a conjecture that offers a gap-one bound for the smallest number of colors needed to equitably color every block graph. In other words, the difference between the upper and the lower bounds of our conjecture is at most one. Thus, in some sense, the situation is similar to that of chromatic index, where we have the classical theorem of Vizing and the Goldberg conjecture for multigraphs. The results obtained in the paper support our conjecture. More precisely, we verify it in the class of well-covered block graphs, which are block graphs in which each vertex belongs to a maximum independent set. We also show that the conjecture is true for block graphs, which contain a vertex that does not lie in an independent set of size larger than two. Finally, we verify the conjecture for some symmetric-like block graphs. In order to derive our results we obtain structural characterizations of block graphs from these classes.

preprint2014arXiv

Equitable coloring of corona products of cubic graphs is harder than ordinary coloring

A graph 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 $k$ for which such a coloring exists is known as the \emph{equitable chromatic number} of $G$ and it is denoted by $χ_{=}(G)$ . In this paper the problem of determinig $χ_=$ for coronas of cubic graphs is studied. Although the problem of ordinary coloring of coronas of cubic graphs is solvable in polynomial time, the problem of equitable coloring becomes NP-hard for these graphs. We provide polynomially solvable cases of coronas of cubic graphs and prove the NP-hardness in a general case. As a by-product we obtain a simple linear time algorithm for equitable coloring of such graphs which uses $χ_=(G)$ or $χ_=(G)+1$ colors. Our algorithm is best possible, unless $P=NP$ . Consequently, cubical coronas seem to be the only known class of graphs for which equitable coloring is harder than ordinary coloring.

preprint2014arXiv

On bipartization of cubic graphs by removal of an independent set

We study a new problem for cubic graphs: bipartization of a cubic graph $Q$ by deleting sufficiently large independent set $I$ . It can be expressed as follows: \emph{Given a connected $n$ -vertex tripartite cubic graph $Q=(V,E)$ with independence number $α(Q)$ , does $Q$ contain an independent set $I$ of size $k$ such that $Q-I$ is bipartite?} We are interested for which value of $k$ the answer to this question is affirmative. We prove constructively that if $α(Q) \geq 4n/10$ , then the answer is positive for each $k$ fulfilling $\lfloor (n-α(Q))/2 \rfloor \leq k \leq α(Q)$ . It remains an open question if a similar construction is possible for cubic graphs with $α(Q)<4n/10$ . Next, we show that this problem with $α(Q)\geq 4n/10$ and $k$ fulfilling inequalities $\lfloor n/3 \rfloor \leq k \leq α(Q)$ can be related to semi-equitable graph 3-coloring, where one color class is of size $k$ , and the subgraph induced by the remaining vertices is equitably 2-colored. This means that $Q$ has a coloring of type $(k, \lceil(n-k)/2\rceil, \lfloor (n-k)/2 \rfloor)$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.