Rok 2018

• On incidence coloring of coloring of complete multipartite and semicubic bipartite graphs

  Publikacja

  • R. Janczewski
  • A. Małafiejska
  • M. Małafiejski

  - Discussiones Mathematicae Graph Theory - Rok 2018

  In the paper, we show that the incidence chromatic number of a complete k-partite graph is at most ∆+2 (i.e., proving the incidence coloring conjecture for these graphs) and it is equal to ∆+1 if and only if the smallest part has only one vertex.

  Pełny tekst do pobrania w portalu

• Total domination in versus paired-domination in regular graphs

  Publikacja

  • J. Cyman
  • M. Dettlaff
  • M. A. Henning
  • M. Lemańska
  • J. Raczek

  - Discussiones Mathematicae Graph Theory - Rok 2018

  A subset S of vertices of a graph G is a dominating set of G if every vertex not in S has a neighbor in S, while S is a total dominating set of G if every vertex has a neighbor in S. If S is a dominating set with the additional property that the subgraph induced by S contains a perfect matching, then S is a paired-dominating set. The domination number, denoted γ(G), is the minimum cardinality of a dominating set of G, while the...

  Pełny tekst do pobrania w portalu

Rok 2019

• Domination subdivision and domination multisubdivision numbers of graphs

  Publikacja

  • M. Dettlaff
  • J. Raczek
  • J. Topp

  - Discussiones Mathematicae Graph Theory - Rok 2019

  The domination subdivision number sd(G) of a graph G is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number of G. It has been shown [10] that sd(T)<=3 for any tree T. We prove that the decision problem of the domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the domination multisubdivision number...

  Pełny tekst do pobrania w portalu

Rok 2020

• A note on polynomial algorithm for cost coloring of bipartite graphs with Δ ≤ 4

  Publikacja

  • K. Giaro
  • M. Kubale

  - Discussiones Mathematicae Graph Theory - Rok 2020

  In the note we consider vertex coloring of a graph in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of coloring is the sum of costs incurred at each vertex. We show that the minimum cost coloring problem for n-vertex bipartite graph of degree ∆≤4 can be solved in O(n^2) time. This extends Jansen’s result [K.Jansen,The optimum cost chromatic partition problem, in:...

  Pełny tekst do pobrania w portalu

• Graph classes generated by Mycielskians

  Publikacja

  • M. Borowiecki
  • P. Borowiecki
  • E. Drgas-Burchardt
  • E. Sidorowicz

  - Discussiones Mathematicae Graph Theory - Rok 2020

  In this paper we use the classical notion of weak Mycielskian M'(G) of a graph G and the following sequence: M'_{0}(G) =G, M'_{1}(G)=M'(G), and M'_{n}(G)=M'(M'_{n−1}(G)), to show that if G is a complete graph oforder p, then the above sequence is a generator of the class of p-colorable graphs. Similarly, using Mycielskian M(G) we show that analogously defined sequence is a generator of the class consisting of graphs for which the...

  Pełny tekst do pobrania w portalu

Rok 2021

• Block graphs with large paired domination multisubdivision number

  Publikacja

  • C. M. Mynhardt
  • J. Raczek

  - Discussiones Mathematicae Graph Theory - Rok 2021

  The paired domination multisubdivision number of a nonempty graph G, denoted by msdpr(G), is the smallest positive integer k such that there exists an edge which must be subdivided k times to increase the paired domination number of G. It is known that msdpr(G) ≤ 4 for all graphs G. We characterize block graphs with msdpr(G) = 4.

  Pełny tekst do pobrania w portalu

• T-colorings, divisibility and circular chromatic number

  Publikacja

  • R. Janczewski
  • A. M. Trzaskowska
  • K. Turowski

  - Discussiones Mathematicae Graph Theory - Rok 2021

  Let T be a T-set, i.e., a finite set of nonnegative integers satisfying 0 ∈ T, and G be a graph. In the paper we study relations between the T-edge spans espT (G) and espd⊙T (G), where d is a positive integer and d ⊙ T = {0 ≤ t ≤ d (max T + 1): d |t ⇒ t/d ∈ T} . We show that espd⊙T (G) = d espT (G) − r, where r, 0 ≤ r ≤ d − 1, is an integer that depends on T and G. Next we focus on the case T = {0} and show that espd⊙{0} (G) =...

  Pełny tekst do pobrania w portalu

Rok 2023

• Restrained differential of a graph

  Publikacja

  • A. Cabrera-Martinez
  • M. Dettlaff
  • M. Lemańska
  • J. A. Rodriguez-Velazquez

  - Discussiones Mathematicae Graph Theory - Rok 2023

  Given a graph $G=(V(G), E(G))$ and a vertex $v\in V(G)$, the {open neighbourhood} of $v$ is defined to be $N(v)=\{u\in V(G) :\, uv\in E(G)\}$. The {external neighbourhood} of a set $S\subseteq V(G)$ is defined as $S_e=\left(\cup_{v\in S}N(v)\right)\setminus S$, while the \emph{restrained external neighbourhood} of $S$ is defined as $S_r=\{v\in S_e : N(v)\cap S_e\neq \varnothing\}$. The restrained differential of a graph $G$ is...

  Pełny tekst do pobrania w portalu