Concept

Total coloring

Related publications (26)

The Power of Two Matrices in Spectral Algorithms for Community Recovery

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...

Ieee-Inst Electrical Electronics Engineers Inc2024

Differentially private multi-agent constraint optimization

Boi Faltings, Aleksei Triastcyn, Sankarshan Damle, Sujit Prakash Gujar

Distributed constraint optimization (DCOP) is a framework in which multiple agents with private constraints (or preferences) cooperate to achieve a common goal optimally. DCOPs are applicable in several multi-agent coordination/allocation problems, such as ...

Springer2024

Differentially Private Multi-Agent Constraint Optimization

Boi Faltings, Sujit Prakash Gujar, Sankarshan Damle, Aleksei Triastcyn

Several optimization scenarios involve multiple agents that desire to protect the privacy of their preferences. There are distributed algorithms for constraint optimization that provide improved privacy protection through secure multiparty computation. How ...

ACM2022

Edge colorings of graphs without monochromatic stars

Abhishek Methuku

In this note, we improve on results of Hoppen, Kohayakawa and Lefmann about the maximum number of edge colorings without monochromatic copies of a star of a fixed size that a graph on n vertices may admit. Our results rely on an improved application of an ...

Elsevier2020

On the Turan number of ordered forests

Gábor Tardos, Istvan Tomon, Dániel József Korándi

An ordered graph H is a simple graph with a linear order on its vertex set. The corresponding Turan problem, first studied by Pach and Tardos, asks for the maximum number ex(

ACADEMIC PRESS INC ELSEVIER SCIENCE2019

Tight Bounds for Online Edge Coloring

David Wajc

Vizing's celebrated theorem asserts that any graph of maximum degree Delta admits an edge coloring using at most Delta + 1 colors. In contrast, Bar-Noy, Motwani and Naor showed over a quarter century ago that the trivial greedy algorithm, which uses 2 Delt ...

IEEE COMPUTER SOC2019

On the Rainbow Turan number of paths

Abhishek Methuku

Let F be a fixed graph. The rainbow Turan number of F is defined as the maximum number of edges in a graph on n vertices that has a proper edge-coloring with no rainbow copy of F (i.e., a copy of F all of whose edges have different colours). The systematic ...

ELECTRONIC JOURNAL OF COMBINATORICS2019

Distributed Coloring of Graphs with an Optimal Number of Colors

Etienne Michel François Bamas

This paper studies sufficient conditions to obtain efficient distributed algorithms coloring graphs optimally (i.e. with the minimum number of colors) in the LOCAL model of computation. Most of the work on distributed vertex coloring so far has focused on ...

SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS2019

Coordination of Dynamic Software Components with JavaBIP

Simon Bliudze, Anastasia Mavridou

JavaBIP allows the coordination of software components by clearly separating the functional and coordination aspects of the system behavior. JavaBIP implements the principles of the BIP component framework rooted in rigorous operational semantics. Recent w ...

Springer International Publishing2017

The Erdos-Hajnal conjecture for rainbow triangles

János Pach

We prove that every 3-coloring of the edges of the complete graph on n vertices without a rainbow triangle contains a set of order ohm(n(1/3) log(2) n) which uses at most two colors, and this bound is tight up to a constant factor. This verifies a conjectu ...

Academic Press Inc Elsevier Science2015

Triangle-free intersection graphs of line segments with large chromatic number

Bartosz Maria Walczak, Michal Lason

In the 1970s Erdos asked whether the chromatic number of intersection graphs of line segments in the plane is bounded by a function of their clique number. We show the answer is no. Specifically, for each positive integer k we construct a triangle-free fam ...

Academic Press Inc Elsevier Science2014

Coloring Intersection Graphs of Arc-Connected Sets in the Plane

Bartosz Maria Walczak, Michal Lason

A family of sets in the plane is simple if the intersection of any subfamily is arc-connected, and it is pierced by a line L if the intersection of any member with L is a nonempty segment. It is proved that the intersection graphs of simple families of com ...

Springer2014

Coloring Relatives of Interval Overlap Graphs via On-line Games

Bartosz Maria Walczak

The main goal of this paper is to formalize and explore a connection between chromatic properties of graphs defined by geometric representations and competitivity analysis of on-line algorithms. This connection became apparent after the recent construction ...

Springer-Verlag Berlin2014

On some coloring problems in grids

Dominique de Werra

We study complexity issues related to some coloring problems in grids: we examine in particular the case of List coloring, of Precoloring extension and of (p, q)-List coloring, the case of List coloring in bipartite graphs where lists in the first part of ...

2013

Triangle-Free Geometric Intersection Graphs with Large Chromatic Number

Bartosz Maria Walczak, Michal Lason

Several classical constructions illustrate the fact that the chromatic number of a graph may be arbitrarily large compared to its clique number. However, until very recently no such construction was known for intersection graphs of geometric objects in the ...

Springer US2013

A note on chromatic properties of threshold graphs

Dominique de Werra, Bernard Ries, Rico Zenklusen

In threshold graphs one may find weights for the vertices and a threshold value t such that for any subset S of vertices, the sum of the weights is at most the threshold t if and only if the set S is a stable (independent) set. In this note we ask a simila ...

Elsevier2012

An Optimal Linear-Time Algorithm for Interprocedural Register Allocation in High Level Synthesis Using SSA Form

Paolo Ienne, Philip Brisk, Ajay Kumar Verma

An optimal linear-time algorithm for interprocedural register allocation in high level synthesis is presented. Historically, register allocation has been modeled as a graph coloring problem, which is nondeterministic polynomial time-complete in general; ho ...

2010

Graph coloring with cardinality constraints on the neighborhoods

Dominique de Werra, Bernard Ries

Extensions and variations of the basic problem of graph coloring are introduced. The problem consists essentially in finding in a graph G a k-coloring, i.e., a partition V-1,...,V-k of the vertex set of G such that, for some specified neighborhood (N) over ...

2009

A tutorial on the use of graph coloring for some problems in robotics

Dominique de Werra, Tinaz Ekim

We study the problem where a robot has to pick up items of different sizes which are stored along a corridor. A natural requirement is that the items have to be collected in decreasing order of their sizes. We deal with various systems according to the loc ...

2009

Degree-constrained edge partitioning in graphs arising from discrete tomography

Dominique de Werra, Bernard Ries

Starting from the basic problem of reconstructing a 2-dimensional image given by its projections on two axes, one associates a model of edge coloring in a complete bipartite graph. The complexity of the case with k=3 colors is open. Variations and special ...

2009