Source author record

Marcin Anholcer

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

7works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Majority dominator colorings of graphs

Let $G$ be a simple graph of order $n$ . A majority dominator coloring of a graph $G$ is proper coloring in which each vertex of the graph dominates at least half of one color class. The majority dominator chromatic number $χ_{md}(G)$ is the minimum number of color classes in a majority dominator coloring of $G$ . In this paper we study properties of the majority dominator coloring of a graph. We obtain tight upper and lower bounds in terms of chromatic number, dominator chromatic number, maximum degree, domination and independence number. We also study majority dominator coloring number of selected families of graphs.

preprint2020arXiv

Majority choosability of countable graphs

In any vertex coloring of a graph some edges have differently colored ends (\emph{good} edges) and some are monochromatic (\emph{bad} edges). In a proper coloring all edges are good. In a \emph{majority coloring} it is enough that for every vertex $v$ , the number of bad edges incident to $v$ does not exceed the number of good edges incident to $v$ . A well known result of Lovász \cite{Lovasz} asserts that every finite graph has a majority $2$ -coloring. A similar statement for countably infinite graphs is a challenging open problem, known as the \emph{Unfriendly Partition Conjecture}. We consider a natural list variant of majority coloring. A graph is \emph{majority $k$ -choosable} if it has a majority coloring from any lists of size $k$ assigned arbitrarily to the vertices. We prove that every countable graph is majority $4$ -choosable. We also consider a natural analog of majority coloring for directed graphs. We prove that every countable digraph is also majority $4$ -choosable. We pose list and directed analogs of the Unfriendly Partition Conjecture, stating that every countable graph is majority $2$ -choosable and every countable digraph is majority $3$ -choosable.

preprint2016arXiv

Group Sum Chromatic Number of Graphs

We investigate the \textit{group sum chromatic number} ($\gchi(G)$) of graphs, i.e. the smallest value $s$ such that taking any Abelian group $\gr$ of order $s$ , there exists a function $f:E(G)\rightarrow \gr$ such that the sums of edge labels properly colour the vertices. It is known that $\gchi(G)\in\{χ(G),χ(G)+1\}$ for any graph $G$ with no component of order less than $3$ and we characterize the graphs for which $\gchi(G)=χ(G)$.

preprint2012arXiv

Distance magic labeling and two products of graphs

Let $G=(V,E)$ be a graph of order $n$ . A distance magic labeling of $G$ is a bijection $\ell \colon V\rightarrow {1,...,n}$ for which there exists a positive integer $k$ such that $\sum_{x\in N(v)}\ell (x)=k$ for all $v\in V$ , where $N(v)$ is the neighborhood of $v$ . We introduce a natural subclass of distance magic graphs. For this class we show that it is closed for the direct product with regular graphs and closed as a second factor for lexicographic product with regular graphs. In addition, we characterize distance magic graphs among direct product of two cycles.

preprint2012arXiv

Group Irregularity Strength of Connected Graphs

We investigate the group irregularity strength ( $s_g(G)$ ) of graphs, i.e. the smallest value of $s$ such that taking any Abelian group $\gr$ of order $s$ , there exists a function $f:E(G)\rightarrow \gr$ such that the sums of edge labels at every vertex are distinct. We prove that for any connected graph $G$ of order at least 3, $s_g(G)=n$ if $n\neq 4k+2$ and $s_g(G)\leq n+1$ otherwise, except the case of some infinite family of stars.

preprint2011arXiv

Irregular Labellings of Circulant Graphs

We investigate the \textit{irregularity strength} ( $s(G)$ ) and \textit{total vertex irregularity strength} ( $tvs(G)$ ) of circulant graphs $Ci_n(1,2,...,k)$ and prove that $tvs(Ci_n(1,2,...,k))=\lceil\frac{n+2k}{2k+1}\rceil$ , while $s(Ci_n(1,2,...,k))=\lceil\frac{n+2k-1}{2k}\rceil$ except the case when $(n \bmod 4k = 2k+1 \wedge k\bmod 2=1) \vee n=2k+1$ and $s(Ci_n(1,2,...,k))=\lceil\frac{n+2k-1}{2k}\rceil+1$ .

preprint2011arXiv

Total Vertex Irregularity Strength of Forests

We investigate a graph parameter called the total vertex irregularity strength ( $tvs(G)$ ), i.e. the minimal $s$ such that there is a labeling $w: E(G)\cup V(G)\rightarrow \{1,2,..,s\}$ of the edges and vertices of $G$ giving distinct weighted degrees $wt_G(v):=w(v)+\sum_{v\in e \in E(G)}w(e)$ for every pair of vertices of $G$ . We prove that $tvs(F)=\lceil (n_1+1)/2 \rceil$ for every forest $F$ with no vertices of degree 2 and no isolated vertices, where $n_1$ is the number of pendant vertices in $F$ . Stronger results for trees were recently proved by Nurdin et al.

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.