The problem of testing if a graph can be colored with a given number k of colors is NP-complete for every k>2. But what if we have more information about the input graph, namely that some fixed graph H is not present in it as an induced subgraph? It is known that the problem remains NP-complete even for k=3, unless H is the disjoint union of paths.
We consider the following two questions:
1) For which graphs H is there a polynomial time algorithm to 3-color (or in general k-color) an H-free graph?
2) For which graphs H are there finitely many 4-critical H-free graphs?
This talk will survey recent progress on these questions, and in particular give a complete answer to the second one.

One practical difficulty in computing a solution to some combinatorial optimization problem is that the data might be known only within some interval of uncertainty. In some cases it might be possible to tests specific variables of the input and obtain their exact value. A natural task in this model is to minimize the number of tests until it is possible to produce an optimal solution. This problem has been addressed in the context of computing a minimum spanning tree for a graph where edge weights are given within some uncertainty intervals, but also for the knapsack problem and a single-machine scheduling problem. In the later the processing time of a job can potentially be reduced (by an a priori unknown amount) by testing the job. Testing a job $j$ takes one unit of time and may reduce its processing time from the given upper limit $\bar{p}_j$ (which is the time taken to execute the job if it is not tested) to any value between $0$ and $\bar{p}_j$. This setting is motivated e.g. by applications where a code optimizer can be run on a job before executing it. This talk with be a gentle introduction into this new model, reveal key algorithmic ideas and present more in detail the later scheduling problem.

Given a class A of graphs and a decision problem X belonging to NP, we say that a full complexity dichotomy of A was obtained if one describes a partition of A into subclasses such that X is classified as polynomial or NP-complete when restricted to each subclass. The concept of full complexity dichotomy is particularly interesting for the investigation of NP-complete problems: as we partition a class A into NP-complete subclasses and polynomial subclasses, it becomes clearer why the problem is NP-complete in A. The class C of graphs that do not contain a cycle with a unique chord was studied by Trotignon and Vušković who proved a structure theorem which led to solving the vertex-colouring problem in polynomial time. We apply the structure theorem to study the complexity of edge-colouring and total-colouring, and show that even for graph classes with strong structure and powerful decompositions, the edge-colouring problem may be difficult. We discuss several surprising complexity dichotomies found in subclasses of C, and the concepts of separating class and of separating problems.

Random hyperbolic graphs (RHG) were proposed rather recently (2010) as a model of real-world networks. Informally speaking, they are like random geometric graphs where the underlying metric space has negative curvature (i.e., is hyperbolic). In contrast to other models of complex networks, RHG simultaneously and naturally exhibit characteristics such as sparseness, small diameter, non-negligible clustering coefficient and power law degree distribution. We will give a slow pace introduction to RHG, explain why they have attracted a fair amount of attention and then survey most of what is known about this promising infant model of real-world networks.

Robinsonian matrices are structured matrices that have been introduced in the 1950's by the archeologist W.S. Robinson for chronological dating of Egyptian graves.
A symmetric matrix is said to be Robinsonian if its rows and columns can be simultaneously reordered in such a way that the entries are monotone nondecreasing in the rows and columns when moving toward the main diagonal. Robinsonian matrices can be seen as a matrix analog of unit interval graphs, which are precisely the graphs having a Robinsonian adjacency matrix. We will discuss several aspects of Robinsonian matrices: links to unit interval graphs; new efficient combinatorial recognition algorithm based on Similarity-First Search, a natural extension to weighted graphs of Lex-BFS; structural characterization by minimal forbidden substructures; and application to tractable instances of the Quadratic Assignment Problem.

A $b$-coloring of a graph $G$ is a proper coloring such that every color class has a vertex with neighbors in each other color class. The $b$-chromatic number of $G$ is the maximum integer $k$ such that $G$ admits a $b$-coloring with $k$ colors. This parameter was introduced by Irving and Manlove in 1999. In that work, they proved that the related decision problem is $NP$-complete while polynomial on trees. In this talk, we start by relating the $b$-chromatic number of $G$ with its other chromatic numbers issued of other heuristics. Then, we recall some structural properties of graphs which directly impact their $b$-chromatic number and other related parameters, such as girth, maximum degree, $m$-degree and forbidden subgraphs. In particular, we are going to see how the good structural behavior of product of graphs impact some parameters related to $b$-colorings. We finish this talk by showing two recently defined $b$-colorings parameters, namely $b$-homomorphism and partial $b$-coloring and some of their open problems of general interest.

A perfect phylogeny is a rooted tree representing the evolutionary history of a set of n objects. The objects bijectively label the leaves of the tree and there are m binary characters, each labeling exactly one edge of the tree. For each leaf, the set of characters that appear on the unique root-to-leaf path is the set of characters taking value 1 at the object labeling the leaf. While every perfect phylogeny naturally corresponds to an n x m binary matrix having objects as rows and characters as columns, the perfect phylogeny problem asks the opposite question: Does a given binary matrix correspond to a perfect phylogeny? The problem is well known to be polynomially solvable: the yes instances are characterized by the absence of pairs of conflicting columns, where two columns of a binary matrix are said to be in conflict if there exist three rows on which the two columns read 11, 10, and 01, respectively. The perfect phylogeny problem and various generalizations of it -many of which were proved intractable- have been extensively studied in computational biology.
We will discuss two generalizations of the perfect phylogeny problem, first considered by Hajirasouliha and Raphael in 2014 and motivated by applications in cancer genomics. Both problems are optimizations problems and can be defined as follows:

• The minimum conflict-free row split (MCRS) problem: split each row of a given binary matrix into a bitwise OR of a set of rows so that the resulting matrix has no pairs of conflicting columns (that is, it corresponds to a perfect phylogeny) and has the minimum number of rows among all matrices with this property.
• The minimum distinct conflict-free row split problem: the variant of the problem in which the task is to minimize the number of distinct rows of the resulting matrix.

The talk will focus on various graph theoretic and computational aspects of the two problems, including:

• formulations of the two problems in terms of branchings in a derived directed acyclic graph,
• a related characterization of cocomparability graphs,
• inapproximability results and approximation algorithms for the two problems,
• two polynomial time heuristic algorithms for the MCRS problem: an algorithm based on coloring cocomparability graphs, and an improvement of it that finds an optimal solution in a reduced search space via a new min-max result in weighted acyclic digraphs generalizing Dilworth's theorem.

The results presented in the talk were obtained in collaborations with Ademir Hujdurović, Edin Husić, Urša Kačar, Bernard Ries, Romeo Rizzi, and Alexandru I. Tomescu.

We present new results concerning restricted types of matchings such as uniquely restricted matchings and acyclic matchings, and we also consider the corresponding edge coloring notions. Our focus lies on bounds, exact and approximative algorithms. Furthermore, we discuss some matching removal problems.
The talk is based on joined work with J. Baste, C. Lima, L. Penso, I. Sau, U. Souza, and J. Szwarcfiter.

Given a family of arcs on a circle, its \emph{intersection graph} has one vertex for each set of the family, and two of its vertices are adjacent if and only if the corresponding arcs have nonempty intersection. A family of arcs on a circle is \emph{Helly} if every nonempty subfamily of mutually intersecting arcs has nonempty intersection. A family of arcs on a circle is \emph{normal} if no two arcs of the family cover the whole circle.
A graph is a \emph{circular-arc graph} if it is the intersection graph of a family of arcs on a circle. If the family of arcs can be chosen to be Helly, the graph is called a \emph{Helly circular-arc graph}. If the family can be chosen to be Helly and normal simultaneously, the graph is known as a \emph{normal Helly circular-arc graph}.
A graph is \emph{concave-round} (sometimes also a \emph{Tucker circular-arc graph}) if there is an arrangement of its vertices on a circle in such a way that the closed neighborhood of each vertex (i.e., the set consisting of the vertex and its neighbors) forms an arc in the circular arrangement.
In this talk, we will present some results on Helly circular-arc graphs, normal Helly circular-arc graphs, and concave-round graphs. We will discuss minimal forbidden induced subgraph characterizations as well as linear-time algorithms for finding one of the corresponding forbidden subgraphs.
Results on normal Helly circular-arc graphs are joint work with Yixin Cao and Luciano Grippo.

The partially disjoint paths problem asks for paths P_1,...,P_k between given pairs of terminals, while certain pairs of paths P_i,P_j are required to be disjoint. With the help of combinatorial group theory, we show that, for fixed k, this problem can be solved in polynomial time for planar directed graphs. We also discuss related problems.
No specific foreknowledge is required.

During the last five years, a series of improvements have been made concerning approximation algorithms for the Traveling Salesman Problem: for the special case of distance metrics of graphs (graph-TSP), for the generalization where the salesman starts from and arrives at different fixed vertices (general s-t-path TSP), and for proving some weaker versions of the forty years old "general, four-third-approximation-and-gap conjecture" (uniform covers by tours).

While Matching Theory is a usual tool for the TSP, in the most recent improvements two other pillars of combinatorial optimization appeared: matroids (intersection and union), and polyhedra, in a new way, providing links between the TSP and classical, exact combinatorial optimization.

In this talk I wish to tell some successful ideas, report about our most recent improvements and mention some old and new conjectures.