6 papers
On 3-colorability of (claw, diamond)-free graphs
Nadzieja Hodur, Monika Pilśniak, Magdalena Prorok +1
The -colorability problem is a well-known NP-complete problem and it remains NP-complete for -free graphs. Recently, -colorability has been also conside…
Quasi-majority neighbor sum distinguishing edge-colorings
Rafał Kalinowski, Monika Pilśniak, Elżbieta Sidorowicz +1
In this paper, a -edge-coloring of is any mapping . The edge-coloring of naturally defines a vertex-coloring ,…
On -colorability of -free graphs
Nadzieja Hodur, Monika Pilśniak, Magdalena Prorok +1
The -colorability problem is a well-known NP-complete problem and it remains NP-complete for -free graphs, where a is the graph consisting of a with two penda…
Distinguishing finite and infinite trees of arbitrary cardinality
Wilfried Imrich, Rafał Kalinowski, Florian Lehner +2
Let be a finite or infinite graph and the minimum number of vertices moved by the non-identity automorphisms of . We are interested in bounds on the supremum o…
Distinguishing symmetric digraphs by proper arc-colourings of type I
Rafał Kalinowski, Monika Pilśniak, Magdalena Prorok
A symmetric digraph is obtained from a simple graph by replacing each edge with a pair of opposite arcs , . An arc-…
On the distinguishing chromatic number in hereditary graph classes
Christoph Brause, Rafał Kalinowski, Monika Pilśniak +1
The distinguishing chromatic number of a graph , denoted , is the minimum number of colours in a proper vertex colouring of that is preserved by the identity automor…