Woźniak, Mariusz
Loading...
Email Address
Employee
aktywny
Alternative name
Discipline
matematyka
Author Profiles
Systemy AGH
3 results
Search Results
Now showing 1 - 3 of 3
Item type:Article, Access status: Open Access , Recursively arbitrarily vertex-decomposable suns(2011) Baudon, Olivier; Gilbert, Frédéric; Woźniak, MariuszA graph $G = (V,E)$ is arbitrarily vertex decomposable if for any sequence τ of positive integers adding up to $|V|$, there is a sequence of vertex-disjoint subsets of $V$ whose orders are given by $\tau$, and which induce connected graphs. The aim of this paper is to study the recursive version of this problem on a special class of graphs called suns. This paper is a complement of [O. Baudon, F. Gilbert, M. Woźniak, Recursively arbitrarily vertex-decomposable graphs, research report, 2010].Item type:Article, Access status: Open Access , Local irregularity conjecture for 2-multigraphs versus cacti(Wydawnictwa AGH, 2024) Grzelec, Igor; Woźniak, MariuszA multigraph is locally irregular if the degrees of the end-vertices of every multiedge are distinct. The locally irregular coloring is an edge coloring of a multigraph $G$ such that every color induces a locally irregular submultigraph of $G$. A locally irregular colorable multigraph $G$ is any multigraph which admits a locally irregular coloring. We denote by $\textrm{lir}(G)$ the locally irregular chromatic index of a multigraph $G$, which is the smallest number of colors required in the locally irregular coloring of the locally irregular colorable multigraph $G$. In case of graphs the definitions are similar. The Local Irregularity Conjecture for 2-multigraphs claims that for every connected graph $G$, which is not isomorphic to $K_2$, multigraph $^{2}G$ obtained from $G$ by doubling each edge satisfies $\textrm{lir}(^2G)\leq 2$. We show this conjecture for cacti. This class of graphs is important for the Local Irregularity Conjecture for 2-multigraphs and the Local Irregularity Conjecture which claims that every locally irregular colorable graph $G$ satisfies $\textrm{lir}(G)\leq 3$. At the beginning it has been observed that all not locally irregular colorable graphs are cacti. Recently it has been proved that there is only one cactus which requires 4 colors for a locally irregular coloring and therefore the Local Irregularity Conjecture was disproved.Item type:Article, Access status: Open Access , Recursively arbitrarily vertex-decomposable graphs(2012) Baudon, Olivier; Gilbert, Frédéric; Woźniak, MariuszA graph $G=(V,E)$ is arbitrarily vertex decomposable if for any sequence $\tau$ of positive integers adding up to $|V|$, there is a sequence of vertex-disjoint subsets of $V$ whose orders are given by $\tau$, and which induce connected graphs. The main aim of this paper is to study the recursive version of this problem. We present a solution for trees, suns, and partially for a class of 2-connected graphs called balloons.