Zobrazeno 1 - 10
of 129
pro vyhledávání: '"Pilśniak Monika"'
Autor:
Pilsniak, Monika, Wozniak, Mariusz
We consider edge colorings of a graph in such a way that each two different triangles have distinct colorings. It is an extension of the well-known idea of distinguishing all maximal stars in a graph. It was introduced in literature in 1985 and studi
Externí odkaz:
http://arxiv.org/abs/2407.19050
The $3$-colourability problem is a well-known NP-complete problem and it remains NP-complete for $bull$-free graphs, where $bull$ is the graph consisting of $K_3$ with two pendant edges attached to two of its vertices. In this paper we study $3$-colo
Externí odkaz:
http://arxiv.org/abs/2404.12515
A majority edge-coloring of a graph without pendant edges is a coloring of its edges such that, for every vertex $v$ and every color $\alpha$, there are at most as many edges incident to $v$ colored with $\alpha$ as with all other colors. We extend s
Externí odkaz:
http://arxiv.org/abs/2312.00922
Let $G$ and $H$ be graphs and let $f \colon V(G)\rightarrow V(H)$ be a function. The Sierpi\'{n}ski product of $G$ and $H$ with respect to $f$, denoted by $G \otimes _f H$, is defined as the graph on the vertex set $V(G)\times V(H)$, consisting of $|
Externí odkaz:
http://arxiv.org/abs/2309.15409
Let $C_{n_1}\cup C_{n_2}\cup \ldots \cup C_{n_k}$ be a 2-factor i.e. a vertex-disjoint union of cycles. In this note we completely characterize those 2-factors that are uniquely embeddeble in their complement.
Comment: 16 pages, 12 figures
Comment: 16 pages, 12 figures
Externí odkaz:
http://arxiv.org/abs/2304.12915
A graph $G$ is asymmetrizable if it has a set of vertices whose setwise stablizer only consists of the identity automorphism. The motion $m$ of a graph is the minimum number of vertices moved by any non-identity automorphism. It is known that infinit
Externí odkaz:
http://arxiv.org/abs/2301.10380
Autor:
Bock, Felix, Kalinowski, Rafał, Pardey, Johannes, Pilśniak, Monika, Rautenbach, Dieter, Woźniak, Mariusz
We propose the notion of a majority $k$-edge-coloring of a graph $G$, which is an edge-coloring of $G$ with $k$ colors such that, for every vertex $u$ of $G$, at most half the edges of $G$ incident with $u$ have the same color. We show the best possi
Externí odkaz:
http://arxiv.org/abs/2205.11125
Publikováno v:
In Applied Mathematics and Computation 1 May 2024 468
A vertex colouring of a graph is called asymmetric if the only automorphism which preserves it is the identity. Tucker conjectured that if every automorphism of a connected, locally finite graph moves infinitely many vertices, then there is an asymme
Externí odkaz:
http://arxiv.org/abs/1912.02560
Publikováno v:
Europ. J. Combin. 84 (2020) 103145
An edge-colouring of a graph is distinguishing, if the only automorphism which preserves the colouring is the identity. It has been conjectured that all but finitely many connected, finite, regular graphs admit a distinguishing edge-colouring with tw
Externí odkaz:
http://arxiv.org/abs/1911.11105