8 papers
Arboricity Nearly Bounds Degeneracy
Michał Lasoń, Bartłomiej Bosek, Grzegorz Gutowski +1
Arboricity and degeneracy are two fundamental and closely related graph parameters that measure the sparsity of a graph. Every -degenerate graph is -arboric, but some -arb…
On Strong Majority Edge Colourings with Few Colours
Paweł Pękała, Jakub Przybyło
A strong majority edge colouring of a graph is an edge colouring in which, for every edge and every colour , at most half the edges adjacent to receive colour . L…
Asymptotically Tight Bound for the Conflict-Free Chromatic Index
Mateusz Kamyczura, Jakub Przybyło
The conflict-free chromatic index of a graph is the minimum number of colours in an edge colouring of such that the neighbourhood of every edge contains a colour appearing…
On asymptotically tight bounds for the open conflict-free chromatic indexes of nearly regular graphs
Mateusz Kamyczura, Jakub Przybyło
An edge colouring of a graph is called conflic-free if every non-isolated edge of has a uniquely coloured neighbour in its open edge neighbourhood. The least number of…
On list extensions of the majority edge colourings
Paweł Pękała, Jakub Przybyło
We investigate possible list extensions of generalised majority edge colourings of graphs and provide several results concerning these. Given a graph , a list assignment $…
Alon-Tarsi for hypergraphs
Marcin Anholcer, Bartłomiej Bosek, Grzegorz Gutowski +6
Given a hypergraph , define for every edge a linear expression with arguments corresponding to the vertices. Next, let the polynomial be the product of such…
Degree-balanced decompositions of cubic graphs
Borut Lužar, Jakub Przybyło, Roman Soták
We show that every cubic graph on vertices contains a spanning subgraph in which the number of vertices of each degree deviates from by at most , up…
First-Fit Coloring of Forests in Random Arrival Model
Bartłomiej Bosek, Grzegorz Gutowski, Michał Lasoń +1
We consider a graph coloring algorithm that processes vertices in order taken uniformly at random and assigns colors to them using First-Fit strategy. We show that this algorithm u…