17 citations · 41 across the 15 of their papers we have counts for
16 papers
How to Construct High Barrycades
Jakub Binięda, Michał Dębski, Grzegorz Gutowski +1
Given two positive integers height and order , the barrycade construction problem asks for a set of permutations of the integers from to such that all the proper…
Coloring and Recognizing Directed Interval Graphs
Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Felix Klesen +3
A \emph{mixed interval graph} is an interval graph that has, for every pair of intersecting intervals, either an arc (directed arbitrarily) or an (undirected) edge. We are particul…
Coloring Mixed and Directional Interval Graphs
Grzegorz Gutowski, Florian Mittelstädt, Ignaz Rutter +3
A mixed graph has a set of vertices, a set of undirected egdes, and a set of directed arcs. A proper coloring of a mixed graph is a function that assigns to each vertex in…
Mrs. Correct and Majority Colorings
Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk +3
A majority coloring of a directed graph is a vertex coloring in which each vertex has the same color as at most half of its out-neighbors. In this note we simplify some proof techn…
On a Problem of Steinhaus
Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk +4
Let be a positive integer. A sequence of points in the unit interval is piercing if $\{x_1,x_2,\ldots,x_n\}\cap \left[\frac{i}{n},\frac{i+1}{n}…
Graph Polynomials and Group Coloring of Graphs
Bartłomiej Bosek, Jarosław Grytczuk, Grzegorz Gutowski +2
Let be an Abelian group and let be a simple graph. We say that is -colorable if for some fixed orientation of and every edge labeling , t…
A note on two-colorability of nonuniform hypergraphs
Lech Duraj, Grzegorz Gutowski, Jakub Kozik
For a hypergraph , let denote the expected number of monochromatic edges when the color of each vertex in is sampled uniformly at random from the set of size 2. Let $…
Online Coloring of Short Intervals
Joanna Chybowska-Sokół, Grzegorz Gutowski, Konstanty Junosza-Szaniawski +2
We study the online graph coloring problem restricted to the intersection graphs of intervals with lengths in . For it is the class of unit interval graphs, and for $σ…
The Slow-coloring Game on Sparse Graphs: -Degenerate, Planar, and Outerplanar
Grzegorz Gutowski, Tomasz Krawczyk, Krzysztof Maziarz +3
The \emph{slow-coloring game} is played by Lister and Painter on a graph . Initially, all vertices of are uncolored. In each round, Lister marks a nonempty set of uncolo…
Plane Graphs are Facially-non-repetitively -Choosable
Grzegorz Gutowski
A sequence of even length is a repetition if . We prove existence of a consta…
Defective 3-Paintability of Planar Graphs
Grzegorz Gutowski, Ming Han, Tomasz Krawczyk +1
A -defective -painting game on a graph is played by two players: Lister and Painter. Initially, each vertex is uncolored and has tokens. In each round, Lister marks a…
Lower Bounds for On-line Interval Coloring with Vector and Cardinality Constraints
Grzegorz Gutowski, Patryk Mikos
We propose two strategies for Presenter in the on-line interval graph coloring games. Specifically, we consider a setting in which each interval is associated with a -dimensiona…
The Partial Visibility Representation Extension Problem
Steven Chaplick, Grzegorz Guśpiel, Grzegorz Gutowski +2
For a graph , a function is called a \emph{bar visibility representation} of when for each vertex , is a horizontal line segment (\emph{bar}) and $uv…
Universal targets for homomorphisms of edge-colored graphs
Grzegorz Guśpiel, Grzegorz Gutowski
A -edge-colored graph is a finite, simple graph with edges labeled by numbers . A function from the vertex set of one -edge-colored graph to another is a homomorp…
Chip games and paintability
Lech Duraj, Grzegorz Gutowski, Jakub Kozik
We prove that the difference between the paint number and the choice number of a complete bipartite graph is . That answers the question of Zhu (2009) wh…
Lower bounds for on-line graph colorings
Grzegorz Gutowski, Jakub Kozik, Piotr Micek +1
We propose two strategies for Presenter in on-line graph coloring games. The first one constructs bipartite graphs and forces any on-line coloring algorithm to use …