Andre Raspaud launched in 2005 a fruitful cooperation with the Department of Applied Mathematics of the Sun Yat-Sen University of Kaohsiung, Taiwan. This proposal takes its roots from this three years cooperation (including one PhD student in double doctoral degree scheme). The priority scienti'c theme ?Telecommunications' is a well-known key application area of graph theory. The scienti'c aim of this proposal is to tackle telecommunications problems, especially wireless communications problems, with the help of graph colorings and polyhedral graph theory. A key tool which appears in various related context is graph coloring: wavelength division multiplexing (WDM) networks where colors represent wavelengths, radio networks where colors represent frequencies, fault tolerance where colors represent shared resource risk groups, scheduling problems ... In this project, we intend to study new trends of graph colorings, such as list L(p,q)-colorings, and their implications in telecommunications, especially for channel assignments problems (Task 2, subsection 3.3.3). Clustering introduces a hierarchy that is useful to facilitate routing of information through the network. For dynamic networks such as wireless networks, ef'cient resource management, routing and better throughput performance can be achieved through adaptive clustering of these mobile nodes. Dominating sets and their variants are key graph structures to design clusters, and will be studied in subtask 1.1 (subsection 3.3.2). Stable sets are widely used to model in a so-called con'ict graph, mutually non-con'icting nodes in a network, with respect to some shared ressource. In channel assignment problems, the interference graph is such a con'ict graph. Besides con'ict graphs, computing the maximum size of a stable set does have natural translations in telecommunications issues: the maximum stable set problem on a connectivity graph yields the maximum broadcasting set in a TDMA framework or an activation set in a multihop radio network. In a broadcast schedule for TDMA, different time slots correspond to different colors of a suitable graph coloring: in subtask 1.3, we will investigate this further (subsection 3.3.2, again). The core of our projet is devoted to variations of graph colorings that allow to capture speci'cities of channel assignments problems (subsection 3.3.3). A meaningful example is L(p, q)- labelling which models channel assignment problem in radio networks. Because of their theoretical and practical interests L(p, q)-labellings have received considerable attention. We will study list L(p, q)-labellings, as they are suitable to model channel assignments problems such that the list of available frequencies depends on the transmitter. With the emergence of new technologies like optical technologies, it is necessary to design cheap networks that are reliable. A usual technique to guarantee the survivability of a network in case of failure is to impose the existence of a certain number of disjoint paths between the endnodes of the traf'c demands. Another issue is about the quality of the routing in case of failure. It often happens that the secondary path used to route traf'c between two terminals can be much longer than the usual one, increasing the delay of transmission. To avoid this, it is possible to impose some bound on the paths used for routing informations, depending on the type of rerouting strategy. Polyhedral graph theory turned out to be very helpful to provide ef'cient linear programming based algorithms, for problems with a unique rerouting demand. We will extend this approach to handle several rerouting demands (Task 3, subsection 3.3.4). All participants to this project have a strong commitment to graph theory and will bene't from the expertise of the team Mascotte in telecommunication network design and from the expertise of the team RealOpt in mathematical programming. This project will be especially a great opportunity to establish a collaborative research action between the two INRIA teams RealOpt and Mascotte. It will build a strong research network between french researchers in graph theory (from Bordeaux, Grenoble and Sophia-Antipolis) and the Taiwanese discrete mathematic research community (from the Sun Yat-sen University, the National Taiwan University and Academia Sinica).