# SESSION A1: Graph Theory and Applications

## [181] Formulations for the Balanced Vertex *k*-Separator Problem

Denis Cornaz, Fabio Furini, Mathieu Lacroix, Enrico Malaguti,
A. Ridha Mahjoub and Sébastien Martin

Given an indirected graph *G=(V,E)*, a Vertex *k*-Separator is a subset of the
vertex set *V* such that, when the separator
is removed from the graph, the remaining vertices can be partitioned into *k*
subsets that are pairwise edge-disconnected. In this paper we focus on the Balanced
Vertex *k*-Separator Problem, i.e., the problem of finding a minimum cardinality
separator such that the sizes of the resulting disconnected subsets are balanced.
We present a compact Integer Linear Programming formulation for the problem, and present
a polyhedral study of the associated polytope. We also present an Exponential-Size formulation,
for which we derive a column generation and a branching scheme. Preliminary computational
results are reported comparing the performance of the two formulations on a set of benchmark instances.

## [108] Weighted Dominating Sets and Induced Matchings in Orthogonal Ray Graphs

Asahi Takaoka, Satoshi Tayu and Shuichi Ueno

An orthogonal ray graph is a graph such that for each vertex, there exists an
axis-parallel rays (closed half-lines) in the plane, and two vertices are
adjacent if and only if the corresponding rays intersect. A 2-directional
orthogonal ray graph is an orthogonal ray graph such that the corresponding
ray of each vertex is a rightward ray or a downward ray. We recently showed
in [12] that the weighted dominating set problem can be solved in *O(n ^{4} log n)*
time for vertex-weighted 2-directional orthogonal ray graphs by using a new parameter,
boolean-width of graphs, where

*n*is the number of vertices in a graph. We improve the result by showing an

*O(n*-time algorithm to solve the problem, based on a direct dynamic programming approach. We also show that the weighted induced matching problem can be solved in

^{3})*O(m*time for edge-weighted orthogonal ray graphs, where

^{6})*m*is the number of edges in a graph, closing the gap posed in [12].

## [243] Two bounds of chromatic number in graphs coloring problem

Assia Gueham, Anass Nagih and Hacene Ait Haddadene

In this paper, we essentially focus on the coloration approach and estimation of chromatic number. We propose a first upper bound of a chromatic number based on the orientation algorithm. This upper bound is improved by developing a novel coloration algorithm. Finally, we make a theoretical and empirical comparison of our bounds with Brooks’s bound and Reed’s conjecture for class of triangle-free graphs.