A total coloring is equitable if the number of elements colored with each color differs by
at most one, and the least integer for which a graph has such a coloring is called its equitable
total chromatic number. It is conjectured that the equitable total chromatic number of a
graph is at most Δ + 2, and this has already been proved for cubic graphs. Therefore, the
equitable total chromatic number of a cubic graph is either 4 or 5. In this work we prove
that the problem of deciding whether it is 4 is NP-complete for bipartite cubic graphs.
Furthermore, we establish for one infinite family of Type 1 cubic graphs that they all
have equitable total chromatic number 4.

Keywords: total coloring, equitable total coloring, cubic graphs

A cubic graph is said to be Type 1 if it has total chromatic number equal to 4 and
otherwise it is said to be Type 2. We consider the following question about total colorings
of cubic graphs of large girth: Does there exist a Type 2 cubic graph of girth greater
than 4? Moreover, we formulate a new question about a possible connection between girth
and equitable total colorings: Does there exist a Type 1 cubic graph of girth greater than 4
with equitable total chromatic number 5?
We exhibit infinite families of cubic graphs that indicate that possibly both questions
would have a negative answer. Notice that a negative answer for the first question would
provide a result much stronger than a recent theorem about fractional total colorings of
cubic graphs. In particular, we prove that almost all generalized Petersen graphs are Type 1.
Furthermore, we present a sufficient condition for a cubic graph to be Type 2, contributing
to the search for an answer to the first question.

Due to the increasing globalization and the distant sourcing, reconciling industrial constraints and sales requirements becomes very challenging for industries facing an uncertain environment and demanding customers. The sales and operations planning (S&OP) is crucial for efficiently balancing production capacities with the volatile market demand. In this article, we propose an original S&OP model in order to improve the trade-off between the supply chain costs and the customer satisfaction. The problem is formulated as a multi-objective optimization model with epsilon-constraints and is solved by a simulation-optimization approach. Two classes of policies for managing the parts procurement and the flexibility offered to the sales function are presented. The model and the proposed solution are illustrated with the case study of Renault, a French global automobile manufacturer. Several policies and optimization algorithms are compared in terms of system performance and computation time. Managerial insights are derived based on these results.

A challenge for car manufacturers is to adjust rapidly and efficiently the production capacities with a volatile market demand and despite distant suppliers. In this paper, we consider a sales and operations planning problem based on the actual situation of Renault, a French global automobile manufacturer. The issue is to find the best trade-off between sales requirements and industrial constraints while limiting inventories, emergency supplies and keeping delivery lead times reasonable for customers. A new planning method based on flexibility rates is presented. The flexibility rates are defined to limit orders of a given type of vehicles, during a certain period. A simulation model is introduced and captures the dynamics of the sales and operations management. A numerical study has been performed by using industrial data. Results highlight factors that improve system performances and several policies are compared. This research has also relevance for other industries that face long procurement lead times in an uncertain environment.

We are given a sequence of items that can be packed into $m$ unit size bins and the goal is to assign these items online to m bins while minimizing the stretching factor. Bins have infinite capacities and the stretching factor is the size of the largest bin. We present an algorithm with stretching factor 26/17 improving the best known algorithm by Kellerer and Kotov with a stretching factor 11/7. Our algorithms has 2 stages and uses bunch techniques: we aggregate bins into batches sharing a common purpose.

In this paper an industrial case including a papermill and its three suppliers (sawmills) is studied.
Sawmills produce lumber and chips from wood, and the paper mill needs these chips to make paper.
These sawmills assign a lower priority to the chips market even though the paper mill is their main customer.
The focus of the research is therefore on securing the paper mill supply by creating beneficial contracts for both stakeholders.
Industrial constraints are taken into account, leading to separate contract designs.
Contracts are then tested on various instances and compared to a centralized model that optimizes the total profit of the supply chain.
Results show that the decentralized profit with separate contracts is $99.3\%$ the centralized profit, for a fixed demand variance.
Difference between centralized and decentralized profit slightly increases with the variance, to reach $3\%$ for a variance of $50\%$.

This paper deals with the single-item capacitated lot sizing problem with concave production and storage costs, considering minimum order quantity and dynamic time windows.
This problem models a lot sizing where the production lots are constrained in amount and frequency.
In this problem, a demand must be satisfied at each period t over a planning horizon of T periods.
This demand can be satisfied from the stock or by a production at the same period.
When a production is made at period $t$, the produced quantity must be greater than a minimum order quantity (L) and lower than the production capacity (U).
The frequency constraints on the production lots are modeled by dynamic time windows.
Between two consecutive production lots, there is at least Q periods and at most R periods.
An optimal algorithms in O(T^9) is given.
The complexity of the algorithm is reduced to O(T^7) when all the demands are strictly positive.

Double split graphs form one of the five basic classes in the proof of
the strong perfect graph theorem by Chudnovsky, Robertson, Seymour and
Thomas [The strong perfect graph theorem, Annals of Mathematics
164 (2006) 51–229]. A doubled graph is any induced subgraph of a
double split graph. Alexeev, Fradkin and Kim [Forbidden induced
subgraphs of double-split graphs, SIAM J. Discrete Math. 26
(2012) 1–14] established that the class of doubled graphs is
characterized by a list of 44 forbidden induced graphs of order at
most 9. It follows that deciding if a graph G is a doubled graph
can be done in time O(|V(G)|^9). We show here that this can be done
in time O(|V(G)|+|E(G)|) by analyzing the degree structure of the
graph.

The excessive [m]-index of a graph G is the minimum number of matchings of size m needed to cover the edge-set of G. We call a graph G [m]-coverable if its excessive [m]-index is finite. Obviously the excessive [1]-index is |E(G)| for all graphs and it is an easy task the computation of the excessive [2]-index for a [2]-coverable graph. The case m=3 is completely solved by Cariolaro and Fu in 2009. In this paper we prove a general formula to compute the excessive [4]-index of a tree and we conjecture a possible generalization for any value of m. Furthermore, we prove that such a formula does not work for the excessive [4]-index of an arbitrary graph.

We prove new results for approximating the graphic TSP and some related problems.
We obtain polynomial-time algorithms with improved approximation guarantees.

For the graphic TSP itself, we improve the approximation ratio
to $7/5$.
For a generalization, the connected-$T$-join problem, we
obtain the first nontrivial approximation algorithm, with ratio $3/2$.
This contains the graphic $s$-$t$-path-TSP as a special case.
Our improved approximation guarantee for finding a smallest $2$-edge-connected spanning subgraph is $4/3$.

The key new ingredient of all our algorithms is a special kind of ear-decomposition
optimized using forest representations of hypergraphs.
The same methods also provide the lower bounds (arising from LP relaxations)
that we use to deduce the approximation ratios.

medskip
oindent

oindent{{f keywords:} traveling salesman problem, graphic TSP, $2$-edge-connected subgraph,
$T$-join, ear-decomposition, matroid intersection, forest representation, matching.

A snark is a cyclically-4-edge-connected cubic graph with chromatic index 4. In 1880, Tait proved that the Four-Color Conjecture is equivalent to the statement that every planar bridgeless cubic graph has chromatic index 3. The search for counter-examples to the Four- Color Conjecture motivated the definition of the snarks.
A k-total-coloring of G is an assignment of k colors to the edges and vertices of G, so that adjacent or incident elements have different colors. The total chromatic number of G is the least k for which G has a k-total-coloring. It is known that the total chromatic number of a cubic graph is either 4 or 5. However, the problem of determining the total chromatic number of a graph is NP-hard even for cubic bipartite graphs.
In 2003, Cavicchioli et al. reported that their extensive computer study of snarks shows that all square-free snarks with less than 30 vertices have total chromatic number 4, and asked for the smallest order of a square-free snark with total chromatic number 5.
In this paper we prove that the total chromatic number of both Blanusa families and an infinite snark family (including the Loupekhine and Goldberg snarks) is 4. Relaxing any of the conditions of cyclic-edge-connectivity and chromatic index, we exhibit cubic graphs with total chromatic number 5.
Keywords: snark, total coloring, edge coloring

In this paper we discuss a stochastic scheduling problem with impatience to the beginning of service. The impatience of a job can be seen as a due date and a job is considered to be on time if it begins to be processed before its due-date. Processing times and due dates are random variables. Jobs are processed on a single machine with the objective to minimize the expected weighted number of tardy jobs in the class of static list scheduling policies. We derive optimal schedules when processing times and due dates follow different probability distributions. We also study the relation between the problem with impatience to the beginning of service and the problem with impatience to the end of service. Finally, we provide some additional results for the problem with impatience to the end of service.

A b-coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b-chromatic number b(G) of a graph G is the largest integer k such that G admits a b-coloring with k colors. We show that every graph of order n, different from a clique, satisfies b(G) ? [n + w(G) -1]/2, where w(G) is the maximum clique size in G, and we give a characterization of bipartite graphs that achieve equality in this bound. Also we show that every graph G satisfies b(G) – chi(G) ? [n/2] – 2, and we deduce a characterization of graphs that achieve this bound. In [2] it was shown that if G is a connected graph of order n ? 5, then for every vertex v of G we have b(G-v) ? b(G) + [n/2] – 2. We confirm this result for an arbitrary graph of order n ? 4 and we conjecture that this bound is attained if and only if G = C4, P4 or 2P2.

After use in operating blocs, medical devices (MD) are sent to the sterilization service. The sterilization process is composed of various steps. In the washing step, after predisinfection, different sets of MD, used for different surgical operations, may be washed together without exceeding washer capacity. It is generally not allowed to split MD sets among several washers. In this paper, we model the washing step as a batch scheduling problem, where MD sets are denoted as jobs having different sizes and different release dates, but equal processing times for the washing. The washing steps of sterilization services generally constitute a bottleneck for the entire sterilization process and long pre-disinfection times may corrode MD. Hence, the decisions for batching the MD sets and launching washing cycles are crucial in order to minimize the waiting time of MD in the washing step. First, we provide a MILP model for the minimization of mean pre-disinfection excess time and then a ?-constraint model for the minimization of a second criterion which is the number of washing cycles. Afterwards, two heuristics are developed and experimented on the instances inspired from a real case.

In this paper, we study the problem of minimizing the total duration of the washing operations in hospital sterilization services. After use in operating blocs, reusable medical devices (RMD) are sent to the sterilization service, which is composed of various steps. In the washing step, different sets of RMD, used for different surgeries, may be washed together without exceeding washer capacity. It is generally not allowed to split RMD sets among several washers.
We consider a batch scheduling problem where RMD sets are denoted as jobs having different sizes and different release dates, but equal processing times for the washing. We give optimal algorithms for a special case of the problem where job sizes form a strongly divisible sequence and for another case when job splitting is allowed, respectively. Afterwards, a mixed integer linear programming model is developed for our problem, and an approximation algorithm with worst case ratio of 2 is presented.

This work shows improvements towards effective consideration of scan pre-synthesis. A new algorithm is proposed to optimally decide about scan stitching at RTL. Algorithm efficiency is proven through an industrial RTL-to-GDS design flow and typical design benchmarks.

The chromatic gap is the difference between the chromatic number and the clique number of a graph. Here we investigate gap(n), the maximum chromatic gap over graphs on n vertices. Can the extremal graphs be explored? While computational problems related to the chromatic gap are hopeless, an interplay between Ramsey theory and matching theory leads to a simple and (almost) exact formula for gap(n) in terms of Ramsey numbers. For our purposes it is more convenient to work with the covering gap, the difference between the clique cover number and stability number of a graph and this is what we call the gap of a graph. Then gap(n) can be equivalently defined (by switching from a graph to its complement), as the maximum gap over graphs of n vertices. Notice that the well-studied family of perfect graphs are the graphs whose induced subgraphs have gap zero. Our study is a first step towards better understanding of graphs whose induced subgraphs have gap at most t. The maximum of the (covering) gap and the chromatic gap running on all induced subgraphs will be called perfectness gap.

Using alpha(G) for the cardinality of a largest stable (independent) set of a graph G, we define alpha(n) = min alpha(G) where the minimum is taken over triangle-free graphs on n vertices. It is easy to observe that alpha(n) is essentially an inverse Ramsey function, defined by the relation R(3, alpha(n)) ≤ n < R(3, alpha(n)+1).
Our main result is that gap(n) = ceiling of n/2 – alpha(n), possibly with the exception of small intervals (of length at most 15) around the Ramsey numbers R(3,m), where the error is at most 3.

The central notions in our investigations are the gap-critical and the gap-extremal graphs. A graph G is gap-critical if for every proper induced subgraph H of G, gap(H) < gap(G) and gap-extremal if it is gap-critical with as few vertices as possible (among gap-critical graphs of the same gap). The strong perfect graph theorem, solving a long standing conjecture of Berge that stimulated a broad area of research, states that gap-critical graphs with gap 1 are the holes (chordless odd cycles of length at least five) and antiholes (complements of holes). The next step, the complete description of gap-critical graphs with gap 2 would probably be a very difficult task. As a very first step, we prove that there is a unique 2-extremal graph, 2C5, the union of two disjoint (chordless) cycles of length five.

In general, for t ≥ 0, we denote by s(t) the smallest order of a graph with gap t and we call a graph is t-extremal if it has gap t and order s(t). It is tempting to conjecture that s(t) = 5t with equality for the graph tC5. However, for t ≥ 3 the graph tC5 has gap t but it is not gap-extremal (although gap-critical). We shall prove that s(3) = 13, s(4) = 17 and s(5) is 20 or 21. Somewhat surprisingly, after the uncertain values s(6) in {23, 24, 25}, s(7) in {26, 27, 28}, s(8) in {29, 30 , 31}, s(9) in {32, 33} we can show that s(10) = 35. On the other hand we can easily show that s(t) is asymptotically equal to 2t, that is, gap(n) is asymptotic to n/2. According to our main result the gap is actually equal to ceiling of n/2 – alpha(n), unless n is in an interval [R, R + 14] where R is a Ramsey number, and if this exception occurs the gap may be larger than this value by only a small constant (at most 3).

The definition of s(t) does not change if we replace (covering) gap by chromatic gap, so it can in fact be defined with the perfectness gap as well: it is the smallest order of a graph with perfectness gap equal to t.
Our study shows that triangle-free Ramsey graphs have high matchability and connectivity properties, therewith providing some new properties of the Ramsey-graphs themselves, and leading possibly to new bounds on Ramsey-numbers.

In a graph G = (V, E), the density is the ratio between the number of edges |E| and the number of vertices |V|. This criterion may be used to find communities in a graph: groups of highly connected vertices. We propose an optimization problem based on this criterion, the idea is to find the vertex partition that maximizes the sum of the densities of each class. We prove that this problem is NP-hard by giving a reduction from graph-k-colorability. Additionally, we give a polynomial time algorithm for the special case of trees.

Dans cet article, on s’intéresse à l’étude de la maximisation du profit d’un transporteur de fret. Ce problème intègre la gestion des flux de véhicules simultanément à celle des flux de marchandises.

Nous proposons deux modèles linéaires en nombres entiers, l’un fondé sur des variables arcs pour les véhicules, l’autre sur des variables chemins pour les véhicules, les deux avec des variables arcs pour les marchandises. La comparaison expérimentale de ces deux modèles indique que la formulation « chemin » a une bien meilleure relaxation linéaire que la formulation « arc », réputée faible. Cette dominance est également prouvée par une comparaison théorique des deux modèles.

Through an industrial application, we were confronted with the planning of experiments where human intervention of a chemists is required to handle the starting and termination.
This gives rise to a new type of scheduling problems, namely problems of finding schedules with time periods when the tasks can neither start nor finish. We consider in this paper the natural case of small periods where the duration of the periods is smaller than any processing time. This assumption corresponds to experiments lasting several days whereas the operator unavailability periods are the week-ends. These problems are analyzed on a single machine with the makespan as criterion.
We first prove that, contrary to the case of machine unavailability, the problem with one small operator non-availability period can be solved in polynomial time. We then derive approximation and inapproximability results for the general case of k small unavailability periods. We finally focus on the practical case of periodic and equal small unavailability periods. We prove that this problem is not in FPTAS for more than 3 periods and we derive an FPTAS for the two-period case.

A Gallai-coloring of a complete graph is an edge coloring such that no triangle is colored with three distinct colors. Gallai-colorings occur in various contexts such as the theory of partially ordered sets (in Gallai’s original paper) or information theory. Gallai-colorings extend 2-colorings of the edges of complete graphs. They actually turn out to be close to 2-colorings – without being trivial extensions. Here we give a method to extend some results on 2-colorings to Gallai-colorings, among them known and new, easy and difficult results.

Due to economic and environmental constraints, many organizations have started to ship their products in reusable containers such as plastic pallets, boxes and crates. Minimizing the total flow cost arising from reusable containers is a major problem for these organizations. In this paper we will focus on the modeling of this problem as a network flow, and the proposal of an appropriate resolution method. This resolution method will allow us to better understand the system behavior and can be an important tool for studying related problems, such as dimensioning and purchasing policy.

We call “natural editing of algebraic expressions” the editing of algebraic expressions in their natural representation, the one that is used on paper and blackboard. This is an issue we have investigated in the Aplusix project, a project which develops a system aiming at helping students to learn algebra. The paper summarises first this project. Second it defines the notion of algebraic expression, and of representation of algebraic expression. After an exploration of 20 software systems which represent and edit algebraic expressions, the idea of natural editing of algebraic expressions (insertion, deletion, selection, cut, copy, paste, drag and drop) is presented, leading to the notion of “smart editor”.

In this paper, we address a complete freight transportation problem. The objective function consists of maximizing the carrier profit. It is not necessary to satisfy all demands but profitable demands should be satisfied globally or partially. The carrier needs to ensure a return on his vehicle investment: his vehicles must be neither under- nor over-used. To tackle this industrial problem, we present a model based on a formulation of the Service Network Design with Asset Management problem. Due to the difficulty of finding optimal solutions to this problem, we propose a decomposition of the problem into three main steps: construction of the network, filling vehicles with commodities, construction of the vehicle planning. The resolution of these steps involves heuristic schemes, Mixed Integer Programming and Constraint Programming. We consider different methods for solving these steps and whether to allow transhipment. To evaluate the model and the solution algorithms, we produced instances based on a study of real data. The results show that the methods are robust without transhipment and that transhipment can improve profit.

We analyse the relations between several graph transformations that were introduced to be used in procedures determining the stability number of a graph. We show that all these transformations can be decomposed into a sequence of edge deletions and twin deletions. We also show how some of these transformations are related to the notion of even pair introduced to color some classes of perfect graphs. Then, some properties of edge deletion and twin deletion are given and a conjecture is formulated about the class of graphs for which these transformations can be used to determine the stability number.

A path graph is the intersection graph of subpaths of a tree. In 1970, Renz asked for a characterization of path graphs by forbidden induced subgraphs. We answer this question by determining the complete list of graphs that are not path graphs and are minimal with this property.

In this paper we provide characterizing properties of TDI systems, among others the following: a system of linear inequalities is TDI if and only if its coefficient vectors form a Hilbert basis, and there exists a test-set for the system’s dual integer programs where all test vectors have positive entries equal to $1$. Reformulations of this provide relations between computational algebra and integer programming and they contain Applegate, Cook and McCormick’s sufficient condition for the TDI property and Sturmfels’ theorem relating toric initial ideals generated by square-free monomials to unimodular triangulations. We also study the theoretical and practical efficiency and limits of the characterizations of the TDI property presented here.

In the particular case of set packing polyhedra our results correspond to endowing the weak perfect graph theorem with an additional, computationally interesting, geometric feature: the normal fan of the stable set polytope of a perfect graph can be refined into a regular triangulation consisting only of unimodular cones.

In this paper we consider problems related to Nash-Williams’ Strong Orientation Theorem and Odd-Vertex Pairing Theorem. These theorems date to 1960 and up to now not much is known about their relationship to other subjects in graph theory. We investigated many approaches to find a more transparent proof for these theorems and possibly generalizations of them. In many cases we found negative answers: counter-examples and $NP$-completeness results. For example we show that the weighted and the degree-constrained versions of the well-balanced orientation problem are $NP$-hard. We also show that it is $NP$-hard to find a minimum cost feasible odd-vertex pairing or to decide whether two graphs with some common edges have simultaneous well-balanced orientations or not.

Nash-Williams’ original approach was to define best-balanced orientations with feasible odd-vertex pairings: we show here that not every best-balanced orientation can be obtained this way. However we prove that in the global case this is true: every smooth $k$-arc-connected orientation can be obtained through a $k$-feasible odd-vertex pairing.

The aim of this paper is to help to find a transparent proof for the Strong Orientation Theorem. In order to achieve this we propose some other approaches and raise some open questions, too.

In scheduling literature, the notion of machine non-availability periods is well known, for instance for maintenance. In our case of planning chemical experiments, we have special periods (the week-ends, holidays, vacations) where the chemists are not available. However, human intervention by the chemists is required to handle the starting and termination of the experiments. This gives rise to a new type of scheduling problems, namely problems of finding schedules that respect the operator non-availability periods. These problems are analyzed on a single machine with the makespan as criterion. Properties are described and performance ratios are given for list scheduling algorithms.