6 papers
Finding large -colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs
Nadzieja Hodur, Monika Pilśniak, Magdalena Prorok +1
We study the Max Partial -Coloring problem, where we are given a vertex-weighted graph, and we ask for a maximum-weight induced subgraph that admits a proper -coloring. For $…
On 3-colourability of -free graphs
Nadzieja Hodur, Monika Pilśniak, Magdalena Prorok +1
The -colourability problem is a well-known NP-complete problem and it remains NP-complete for -free graphs, where is the graph consisting of with two pendant…
List majority edge-colorings of graphs
Rafał Kalinowski, Monika Pilśniak, Marcin Stawiski
A majority edge-coloring of a graph without pendant edges is a coloring of its edges such that, for every vertex and every color , there are at most as many edges incident t…
A note on uniquely embeddable 2-factors
Igor Grzelec, Monika Pilśniak, Mariusz Woźniak
Let be a 2-factor i.e. a vertex-disjoint union of cycles. In this note we completely characterize those 2-factors that are uniquely em…
Asymmetrizing infinite trees
Wilfried Imrich, Rafał Kalinowski, Florian Lehner +2
A graph is asymmetrizable if it has a set of vertices whose setwise stablizer only consists of the identity automorphism. The motion of a graph is the minimum number of ver…
Majority Edge-Colorings of Graphs
Felix Bock, Rafał Kalinowski, Johannes Pardey +3
We propose the notion of a majority -edge-coloring of a graph , which is an edge-coloring of with colors such that, for every vertex of , at most half the edge…