2 citations · 5 across the 6 of their papers we have counts for
7 papers · 1 filter
An improvement on the bound for the acyclic chromatic index
Lefteris Kirousis, John Livieratos, Alexandros Singh
The acyclic chromatic index (or acyclic edge-chromatic number) of a graph is the least number of colors needed to properly color its edges so that none of its cycles has only two c…
Improved bounds for acyclic coloring parameters
Lefteris Kirousis, John Livieratos
The {\em acyclic chromatic number} of a graph is the least number of colors needed to properly color its vertices so that none of its cycles has only two colors. The {\em acyclic c…
An Improved Bound of Acyclic Vertex-Coloring
Lefteris Kirousis, John Livieratos
The acyclic chromatic number of a graph is the least number of colors needed to properly color its vertices so that none of its cycles has only two colors. We show that for all $α>…
The Acyclic Chromatic Index is Less than the Double of the Max Degree
Lefteris Kirousis, John Livieratos
The acyclic chromatic index of a graph is the least number of colors needed to properly color its edges so that none of its cycles is bichromatic. In this work, we show that $2…
On the Computational Complexity of Non-dictatorial Aggregation
Lefteris Kirousis, Phokion G. Kolaitis, John Livieratos
We investigate when non-dictatorial aggregation is possible from an algorithmic perspective, where non-dictatorial aggregation means that the votes cast by the members of a society…
Directed Lovász Local Lemma and Shearer's Lemma
Lefteris Kirousis, John Livieratos, Kostas I. Psaromiligkos
Moser and Tardos (2010) gave an algorithmic proof of the lopsided Lovász local lemma (LLL) in the variable framework, where each of the undesirable events is assumed to depend on a…
Aggregation of Votes with Multiple Positions on Each Issue
Lefteris Kirousis, Phokion G. Kolaitis, John Livieratos
We consider the problem of aggregating votes cast by a society on a fixed set of issues, where each member of the society may vote for one of several positions on each issue, but t…