Source author record

Marcin Stawiski

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

3works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

The distinguishing index of graphs with infinite minimum degree

The distinguishing index $D'(G)$ of a graph $G$ is the least number of colors necessary to obtain an edge coloring of $G$ that is preserved only by the trivial automorphism. We show that if $G$ is a connected $α$ -regular graph for some infinite cardinal $α$ then $D'(G) \le 2$ , proving a conjecture of Lehner, Pilśniak, and Stawiski. We also show that if $G$ is a graph with infinite minimum degree and at most $2^α$ vertices of degree $α$ for every infinite cardinal $α$ , then $D'(G) \le 3$ . In particular, $D'(G) \le 3$ if $G$ has infinite minimum degree and order at most $2^{\aleph_0}$ .

preprint2020arXiv

A bound for the distinguishing index of regular graphs

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 two colours. We show that all such graphs except $K_2$ admit a distinguishing edge-colouring with three colours. This result also extends to infinite, locally finite graphs. Furthermore, we are able to show that there are arbitrary large infinite cardinals $κ$ such that every connected $κ$ -regular graph has distinguishing edge-colouring with two colours.

preprint2020arXiv

On asymmetric colourings of graphs with bounded degrees and infinite motion

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 asymmetric colouring with $2$ colours. We make progress on this conjecture in the special case of graphs with bounded maximal degree. More precisely, we prove that if every automorphism of a connected graph with maximal degree $Δ$ moves infinitely many vertices, then there is an asymmetric colouring using $\mathcal O(\sqrt Δ\log Δ)$ colours. This is the first improvement over the trivial bound of $\mathcal O(Δ)$ .

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.