@article {1542, title = {An Exact Cutting Plane Algorithm to Solve the Selective Graph Coloring Problem in Perfect Graphs}, journal = {European Journal of Operational Research}, volume = {291(1)}, year = {2021}, pages = {67{\textendash}83}, doi = {https://doi.org/10.1016/j.ejor.2020.09.017}, author = {Oylum {\c S}eker and Ekim, Tinaz and Z C Ta{\c s}k{\i}n} } @article {1498, title = {The complexity of the defensive domination problem in special graph classes}, journal = {Discrete Mathematics}, volume = {343}, year = {2020}, pages = {111665}, abstract = {

A k-attack on a graph G is a set of k distinct vertices {a1,{\textellipsis},ak} which are said to be under attack. A k-attack A can be countered or defended by a subset of defender vertices X if and only if there exists an injective function f from A to X, such that either f(ai)=ai or (ai,f(ai)) is an edge of G, for all i, 1<=i<=k. Given a graph G, a subset D of V is a k-defensive dominating set of G if and only if D can counter any k-attack in G. We consider the k-defensive dominating set problem. We start a systematic study on the complexity of the k-defensive dominating set problem. When k is not fixed, we show that it is already co-NP-hard to decide whether a given set of vertices is a k-defensive dominating set or not. However, if k is fixed, then we show that the problem is NP-complete even in split graphs. Subsequently, we consider special graph classes, namely paths, cycles, co-chain graphs and threshold graphs. We show that in each of these graph classes, a k-defensive dominating set of minimum size can be found in linear time even for non-fixed k.

}, keywords = {Domination, Networks, Security}, issn = {0012-365X}, doi = {https://doi.org/10.1016/j.disc.2019.111665}, url = {https://www.sciencedirect.com/science/article/pii/S0012365X19303437}, author = {Ekim, Tinaz and Arthur M. Farley and Andrzej Proskurowski} } @article {1499, title = {Mind the independence gap}, journal = {Discrete Mathematics}, volume = {343}, year = {2020}, pages = {111943}, abstract = {

The independence gap of a graph was introduced by Ekim et al.\ in 2018 as a measure of how far a graph is from being well-covered. It is defined as the difference between the maximum and minimum size of a maximal independent set. We investigate the independence gap of a graph from structural and algorithmic points of view, with a focus on classes of perfect graphs. Generalizing results on well-covered graphs due to Dean and Zito (1994) and Hujdurovi{\'c} et al.\ (2018), we express the independence gap of a perfect graph in terms of clique partitions and use this characterization to develop a polynomial-time algorithm for recognizing graphs of constant independence gap in any class of perfect graphs of bounded clique number. Next, we introduce a hereditary variant of the parameter, which we call hereditary independence gap and which measures the maximum independence gap over all induced subgraphs of the graph. We show that determining whether a given graph has hereditary independence gap at most k is polynomial-time solvable if k is fixed and co-NP-complete if k is part of input. We also investigate the complexity of the independent set and independent domination problems in graph classes related to independence gap. In particular, we show that the two problems are NP-complete in the class of graphs of independence gap at most one and that the weighted independent set problem is polynomial-time solvable in any class of graphs with bounded hereditary independence gap. Combined with some known results on claw-free graphs, our results imply that the independent domination problem is solvable in polynomial time in the class of {claw, 2P3}-free graphs.

}, keywords = {Hereditary independence gap, Independent dominating set, Maximal independent set, NP-hard problem, Polynomial-time algorithm, Well-covered graph}, issn = {0012-365X}, doi = {https://doi.org/10.1016/j.disc.2020.111943}, url = {https://www.sciencedirect.com/science/article/pii/S0012365X20301321}, author = {Ekim, Tinaz and Didem G{\"o}z{\"u}pek and Ademir Hujdurovi{\'c} and Martin Milani{\v c}} } @article {1431, title = {A decomposition approach to solve the selective graph coloring problem in some perfect graph families}, journal = {Networks}, volume = {73}, year = {2019}, pages = {145-169}, abstract = {

Graph coloring is the problem of assigning a minimum number of colors to all vertices of a graph such that no two adjacent vertices receive the same color. The selective graph coloring problem is a generalization of the standard graph coloring problem; given a graph with a partition of its vertex set into clusters, the objective is to choose exactly one vertex per cluster so that, among all possible selections, the number of colors necessary to color the vertices in the selection is minimum. This study focuses on a decomposition based exact solution framework for selective coloring in some perfect graph families: in particular, permutation, generalized split, and chordal graphs where the selective coloring problem is known to be NP-hard. Our method combines integer programming techniques and combinatorial algorithms for the graph classes of interest. We test our method on graphs with different sizes and densities, present computational results and compare them with solving an integer programming formulation of the problem by CPLEX, and a state-of-the art algorithm from the literature. Our computational experiments indicate that our decomposition approach significantly improves solution performance in low-density graphs, and regardless of edge-density in the class of chordal graphs.

}, keywords = {chordal graphs, decomposition algorithm, generalized split graphs, integer programming, partition coloring, permutation graphs, selective graph coloring}, doi = {https://doi.org/10.1002/net.21850}, url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/net.21850}, author = {{\c S}eker, Oylum and Ekim, Tinaz and Z C Ta{\c s}k{\i}n} } @article {1501, title = {Edge-stable equimatchable graphs}, journal = {Discrete Applied Mathematics}, volume = {261}, year = {2019}, pages = {136-147}, abstract = {

A graph G is equimatchable if every maximal matching of G has the same cardinality. We are interested in equimatchable graphs such that the removal of any edge from the graph preserves the equimatchability. We call an equimatchable graph G edge-stable if G\e, that is the graph obtained by the removal of edge e from G, is also equimatchable for any e∈E(G). After noticing that edge-stable equimatchable graphs are either 2-connected factor-critical or bipartite, we characterize edge-stable equimatchable graphs. This characterization yields an O(min(n3.376,n1.5m)) time recognition algorithm. Lastly, we introduce and shortly discuss the related notions of edge-critical, vertex-stable and vertex-critical equimatchable graphs. In particular, we emphasize the links between our work and the well-studied notion of shedding vertices, and point out some open questions.

}, keywords = {1-well-covered, Edge-criticality, Edge-stability, Maximal matching, Shedding vertex}, issn = {0166-218X}, doi = {https://doi.org/10.1016/j.dam.2018.09.033}, url = {https://www.sciencedirect.com/science/article/pii/S0166218X18305158}, author = {Zakir Deniz and Ekim, Tinaz} } @article {1500, title = {Small 1-defective Ramsey numbers in perfect graphs}, journal = {Discrete Optimization}, volume = {34}, year = {2019}, pages = {100548}, abstract = {

In this paper, we initiate the study of defective Ramsey numbers for the class of perfect graphs. Let PG be the class of all perfect graphs and R1PG(i,j) denote the smallest n such that all perfect graphs on n vertices have either a 1-dense i-set or a 1-sparse j-set. We show that R1PG(3,j)=j for any j>=2, R1PG(4,4)=6, R1PG(4,5)=8, R1PG(4,6)=10, R1PG(4,7)=13, R1PG(4,8)=15 and R1PG(5,5)=13. We exhibit all extremal graphs for R1PG(4,7)=13 (there are exactly three). We also obtain the 1-defective Ramsey number of order (4,7) in triangle-free perfect graphs, namely R1ΔPG(4,7)=12.

}, keywords = {-dense, -dependent, -sparse, Extremal graphs}, issn = {1572-5286}, doi = {https://doi.org/10.1016/j.disopt.2019.06.001}, url = {https://www.sciencedirect.com/science/article/pii/S1572528618301622}, author = {Ekim, Tinaz and John Gimbel and Oylum {\c S}eker} } @article {1503, title = {On Almost Well-Covered Graphs of Girth at Least 6}, journal = {Discrete Mathematics \& Theoretical Computer Science}, volume = {20}, year = {2018}, author = {Milani{\v c}, Martin and Hujdurovi{\'c}, Ademir and G{\"o}z{\"u}pek, Didem and Ekim, Tinaz} } @article {1509, title = {Equimatchable claw-free graphs}, journal = {Discrete Mathematics}, volume = {341}, year = {2018}, pages = {2859-2871}, abstract = {

A graph is equimatchable if all of its maximal matchings have the same size. A graph is claw-free if it does not have a claw as an induced subgraph. In this paper, we provide the first characterization of claw-free equimatchable graphs by identifying the equimatchable claw-free graph families. This characterization implies an efficient recognition algorithm.

}, keywords = {Connectivity, Equimatchable graph, Factor-critical}, issn = {0012-365X}, doi = {https://doi.org/10.1016/j.disc.2018.06.043}, url = {https://www.sciencedirect.com/science/article/pii/S0012365X18302140}, author = {Saieed Akbari and Hadi Alizadeh and Ekim, Tinaz and Didem G{\"o}z{\"u}pek and Mordechai Shalom} } @article {1504, title = {Graphs of Edge-Intersecting Non-Splitting Paths in a Tree: Representations of Holes-Part II}, journal = {Discrete Mathematics and Theoretical Computer Science}, volume = {20}, year = {2018}, pages = {1b{\textendash}1b}, author = {Boyac{\i}, Arman and Ekim, Tinaz and Shalom, Mordechai and Zaks, Shmuel} } @article {1435, title = {Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem}, journal = {INFORMS Journal on Computing}, volume = {30}, year = {2018}, pages = {43-56}, abstract = {

We investigate the maximum induced matching problem (MIM), which is the problem of finding an induced matching having the largest cardinality on an undirected graph. The problem is known to be NP-hard for general graphs. We first propose a vertex-based integer programming formulation for MIM, which is more compact compared to an edge-based formulation found in the literature. We also introduce the maximum weight induced matching problem (MWIM), which generalizes MIM so that vertices and edges have weights. We adapt the edge-based formulation to MWIM, and propose a quadratic programming formulation of MWIM based on our vertex-based formulation. We then linearize our quadratic programming formulation, and devise a Benders decomposition algorithm that exploits a special structure of the linearized formulation. We also propose valid inequalities and formulation tightening procedures to improve the efficiency of our approach. Our computational tests on a large suite of randomly generated graphs show that our vertex-based formulation and decomposition approach significantly improve the solvability of MIM and MWIM, especially on dense graphs. The online appendix and data are available at https://doi.org/10.1287/ijoc.2017.0764.

}, doi = {10.1287/ijoc.2017.0764}, url = {https://doi.org/10.1287/ijoc.2017.0764}, author = {Ahat, Bet{\"u}l and Ekim, Tinaz and Z C Ta{\c s}k{\i}n} } @article {1502, title = {The maximum cardinality cut problem in co-bipartite chain graphs}, journal = {Journal of Combinatorial Optimization}, volume = {35}, year = {2018}, month = {Jan}, pages = {250{\textendash}265}, issn = {1382-6905}, author = {Ekim, Tinaz and Boyac{\i}, Arman and Shalom, Mordechai} } @article {1507, title = {Complexity of the Improper Twin Edge Coloring of Graphs}, journal = {Graphs and Combinatorics}, volume = {33}, year = {2017}, pages = {595{\textendash}615}, author = {Abedin, Paniz and Akbari, Saieed and Demange, Marc and Ekim, Tinaz} } @proceedings {1180, title = {Edge extremal Graphs Under Degree and Matching Number Restrictions}, journal = {17th Haifa Workshop on Interdisciplinary Applications of Graphs {\textendash} CRI}, year = {2017}, author = {Ekim, Tinaz} } @conference {1185, title = {Linear-Time Generation of Random Chordal Graphs}, booktitle = {International Conference on Algorithms and Complexity}, year = {2017}, publisher = {Springer}, organization = {Springer}, author = {Oylum {\c S}eker and Pinar Heggernes and Ekim, Tinaz and Z. Caner Ta{\c s}k{\i}n} } @article {1508, title = {On matching extendability of lexicographic products}, journal = {RAIRO-Oper. Res.}, volume = {51}, year = {2017}, pages = {857-873}, doi = {10.1051/ro/2016072}, url = {https://doi.org/10.1051/ro/2016072}, author = {Chiarelli, Nina and Dibek, Cemil and Ekim, Tinaz and G{\"o}z{\"u}pek, Didem and Miklavic, Stefko} } @article {1179, title = {Maximum number of edges in claw-free graphs whose maximum degree and matching number are bounded}, journal = {Discrete Mathematics}, volume = {340}, year = {2017}, pages = {927 - 934}, keywords = {Claw-free graphs, Edge-extremal graphs, Maximum matching, Ramsey theory}, issn = {0012-365X}, doi = {https://doi.org/10.1016/j.disc.2017.01.010}, url = {http://www.sciencedirect.com/science/article/pii/S0012365X17300109}, author = {Cemil Dibek and Ekim, Tinaz and Pinar Heggernes} } @article {1506, title = {A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs}, journal = {Information Processing Letters}, volume = {121}, year = {2017}, pages = {29-33}, abstract = {

It is known that the maximum cardinality cut problem is NP-hard even in chordal graphs. On the positive side, the problem is known to be polynomial time solvable in some subclasses of proper interval graphs which is in turn a subclass of chordal graphs. In this paper, we consider the time complexity of the problem in proper interval graphs, and propose a polynomial-time dynamic programming algorithm.

}, keywords = {Graph algorithms, Maximum cut, Proper interval graph}, issn = {0020-0190}, doi = {https://doi.org/10.1016/j.ipl.2017.01.007}, url = {https://www.sciencedirect.com/science/article/pii/S0020019017300133}, author = {Arman Boyac{\i} and Ekim, Tinaz and Mordechai Shalom} } @proceedings {1183, title = {Recent results on equimatchable graphs}, journal = {Combinatorial Potlatch}, year = {2017}, author = {Ekim, Tinaz} } @article {1505, title = {On two extensions of equimatchable graphs}, journal = {Discrete Optimization}, volume = {26}, year = {2017}, pages = {112-130}, abstract = {

A graph is said to be equimatchable if all its maximal matchings are of the same size. In this work we introduce two extensions of the property of equimatchability by defining two new graph parameters that measure how far a graph is from being equimatchable. The first one, called the matching gap, measures the difference between the sizes of a maximum matching and a minimum maximal matching. The second extension is obtained by introducing the concept of equimatchable sets; a set of vertices in a graph G is said to be equimatchable if all maximal matchings of G saturating the set are of the same size. Noting that G is equimatchable if and only if the empty set is equimatchable, we study the equimatchability defect of the graph, defined as the minimum size of an equimatchable set in it. We develop several inapproximability and parameterized complexity results and algorithms regarding the computation of these two parameters, a characterization of graphs of unit matching gap, exact values of the equimatchability defect of cycles, and sharp bounds for both parameters.

}, keywords = {Edge dominating set, Equimatchable graph, Gallai{\textendash}Edmonds decomposition, Minimum maximal matching, Parameterized complexity}, issn = {1572-5286}, doi = {https://doi.org/10.1016/j.disopt.2017.08.002}, url = {https://www.sciencedirect.com/science/article/pii/S1572528616301438}, author = {Zakir Deniz and Ekim, Tinaz and Tatiana Romina Hartinger and Martin Milani{\v c} and Mordechai Shalom} } @article {1178, title = {Equimatchable graphs are C2k+ 1-free for k>= 4}, journal = {Discrete Mathematics}, volume = {339}, year = {2016}, pages = {2964{\textendash}2969}, author = {Dibek, Cemil and Ekim, Tinaz and G{\"o}z{\"u}pek, Didem and Shalom, Mordechai} } @article {1510, title = {Graphs of edge-intersecting and non-splitting paths}, journal = {Theoretical Computer Science}, volume = {629}, year = {2016}, pages = {40-50}, abstract = {

The families of Edge Intersection Graphs of Paths in a tree (resp. in a grid) EPT (resp. EPG) are well studied graph classes. Recently we introduced the class of graphs of Edge-Intersecting and Non-Splitting Paths in a Tree (ENPT) [5]. In this model, two vertices are adjacent if they represent two intersecting paths of a tree whose union is also a path. In this study we generalize this graph class by allowing the host graph to be an arbitrary graph. These are the graphs of Edge-Intersecting and Non-Splitting Paths ENP. Although the Edge Intersection Graphs of Paths in an arbitrary graph includes all graphs, we show that this is not the case for ENP. We also show that the class ENP coincides with the family of graphs of Edge-Intersecting and Non-Splitting Paths in a Grid (ENPG). Following similar studies for EPG graph class, we study the implications of restricting the number of bends of the individual paths in the grid. We show that such a restriction restricts the graph class. Specifically, by restricting the number of bends one gets an infinite sequence of classes such that every class is properly included in the next one.

}, keywords = {EPG graphs, EPT graphs, Intersection graphs}, issn = {0304-3975}, doi = {https://doi.org/10.1016/j.tcs.2015.10.004}, url = {https://www.sciencedirect.com/science/article/pii/S0304397515008750}, author = {Arman Boyac{\i} and Ekim, Tinaz and Mordechai Shalom and Shmuel Zaks} } @article {1170, title = {Graphs of edge-intersecting non-splitting paths in a tree: Representations of holes{\textemdash}Part I}, journal = {Discrete Applied Mathematics}, volume = {215}, year = {2016}, pages = {47{\textendash}60}, author = {Boyac{\i}, Arman and Ekim, Tinaz and Shalom, Mordechai and Zaks, Shmuel} } @article {1172, title = {On the minimum and maximum selective graph coloring problems in some graph classes}, journal = {Discrete Applied Mathematics}, volume = {204}, year = {2016}, pages = {77{\textendash}89}, author = {Demange, Marc and Ekim, Tinaz and Ries, Bernard} } @article {1512, title = {Advances on defective parameters in graphs}, journal = {Discrete Optimization}, volume = {16}, year = {2015}, pages = {62-69}, abstract = {

We consider the generalization of Ramsey numbers to the defective framework using k-dense and k-sparse sets. We construct the first tableaux for defective Ramsey numbers with exact values whenever it is known, and lower and upper bounds otherwise. In light of defective Ramsey numbers, we consider the defective cocoloring problem which consists of partitioning the vertex set of a given graph into k-sparse and k-dense sets. By the help of efficient graph generation methods, we show that c0(4)=12,c1(3)=12 and c2(2)=10 where ck(m) is the maximum order n such that all n-graphs can be k-defectively cocolored using at most m colors. We also give the numbers of k-defective m-cocritical graphs of order n (until n=10) for different levels of defectiveness and m=2,3 and 4.

}, keywords = {Cocritical graphs, Defective cocoloring, Defective Ramsey numbers, Efficient graph generation}, issn = {1572-5286}, doi = {https://doi.org/10.1016/j.disopt.2015.01.002}, url = {https://www.sciencedirect.com/science/article/pii/S1572528615000031}, author = {Ahu Akdemir and Ekim, Tinaz} } @article {1511, title = {On some applications of the selective graph coloring problem}, journal = {European Journal of Operational Research}, volume = {240}, year = {2015}, pages = {307-314}, abstract = {

In this paper we present the Selective Graph Coloring Problem, a generalization of the standard graph coloring problem as well as several of its possible applications. Given a graph with a partition of its vertex set into several clusters, we want to select one vertex per cluster such that the chromatic number of the subgraph induced by the selected vertices is minimum. This problem appeared in the literature under different names for specific models and its complexity has recently been studied for different classes of graphs. Here, we describe different models {\textendash} some already discussed in previous papers and some new ones {\textendash} in very different contexts under a unified framework based on this graph problem. We point out similarities between these models, offering a new approach to solve them, and show some generic situations where the selective graph coloring problem may be used. We focus on specific graph classes motivated by each model, and we briefly discuss the complexity of the selective graph coloring problem in each one of these graph classes and point out interesting future research directions.

}, keywords = {Combinatorial optimization, Computational complexity, Graph theory, partition coloring, Selective coloring}, issn = {0377-2217}, doi = {https://doi.org/10.1016/j.ejor.2014.05.011}, url = {https://www.sciencedirect.com/science/article/pii/S0377221714004184}, author = {Marc Demange and Ekim, Tinaz and Bernard Ries and Cerasela Tanasescu} } @article {ekim2014block, title = {Block decomposition approach to compute a minimum geodetic set}, journal = {RAIRO-Operations Research}, volume = {48}, number = {04}, year = {2014}, pages = {497{\textendash}507}, publisher = {EDP Sciences}, author = {Ekim, Tinaz and Erey, Aysel} } @article {demange2014efficient, title = {Efficient recognition of equimatchable graphs}, journal = {Information Processing Letters}, volume = {114}, number = {1}, year = {2014}, pages = {66{\textendash}71}, publisher = {Elsevier}, author = {Demange, Marc and Ekim, Tinaz} } @article {ekim2014polar, title = {Polar cographs}, journal = {Discrete Applied Mathematics}, volume = {171}, number = {EPFL-ARTICLE-199582}, year = {2014}, pages = {158{\textendash}158}, publisher = {Elsevier Science Bv}, author = {Ekim, Tinaz and Mahadev, NVR and de Werra, Dominique} } @article {BodurEtAl2013, title = {Decomposition Algorithms for Solving the Minimum Weight Maximal Matching Problem}, journal = {Networks}, volume = {62}, number = {4}, year = {2013}, pages = {273{\textendash}287}, doi = {http://dx.doi.org/10.1002/net.21516}, author = {Merve Bodur and Ekim, Tinaz and Z C Ta{\c s}k{\i}n} } @article {boyaci2013graphs, title = {Graphs of Edge-Intersecting Non-splitting Paths in a Tree: Towards Hole Representations}, year = {2013}, author = {Boyac{\i}, Arman and Ekim, Tinaz and Shalom, Mordechai and Zaks, Shmuel} } @article {demange2013hardness, title = {Hardness and approximation of minimum maximal matchings}, journal = {International Journal of Computer Mathematics}, number = {ahead-of-print}, year = {2013}, pages = {1{\textendash}20}, publisher = {Taylor \& Francis}, author = {Demange, Marc and Ekim, Tinaz and Tanasescu, Cerasela} } @article {demange2013note, title = {A note on the NP-hardness of two matching problems in induced subgrids}, journal = {Discrete Mathematics and Theoretical Computer Science}, volume = {15}, number = {2}, year = {2013}, pages = {233{\textendash}242}, author = {Demange, Marc and Ekim, Tinaz and others} } @article {bonomo2013perfectness, title = {Perfectness of clustered graphs}, journal = {Discrete Optimization}, volume = {10}, number = {4}, year = {2013}, pages = {296{\textendash}303}, publisher = {Elsevier}, author = {Bonomo, Flavia and Cornaz, Denis and Ekim, Tinaz and Ries, Bernard} } @article {ekim2013polar, title = {Polar permutation graphs are polynomial-time recognisable}, journal = {European Journal of Combinatorics}, volume = {34}, number = {3}, year = {2013}, pages = {576{\textendash}592}, publisher = {Academic Press}, author = {Ekim, Tinaz and Heggernes, Pinar and Meister, Daniel} } @article {ekim2013some, title = {Some Defective Parameters in Graphs}, journal = {Graphs and Combinatorics}, volume = {29}, number = {2}, year = {2013}, pages = {213{\textendash}224}, publisher = {Springer Japan}, author = {Ekim, Tinaz and Gimbel, John} } @inbook {ekim2012computing, title = {Computing minimum geodetic sets of proper interval graphs}, booktitle = {LATIN 2012: Theoretical Informatics}, year = {2012}, pages = {279{\textendash}290}, publisher = {Springer Berlin Heidelberg}, organization = {Springer Berlin Heidelberg}, author = {Ekim, Tinaz and Erey, Aysel and Heggernes, Pinar and van{\textquoteright}t Hof, Pim and Meister, Daniel} } @article {TaskinEkim2012, title = {Integer Programming Formulations for the Minimum Weighted Maximal Matching Problem}, journal = {Optimization Letters}, volume = {6(6)}, year = {2012}, pages = {1161-1171}, doi = {http://dx.doi.org/10.1007/s11590-011-0351-x}, author = {Z C Ta{\c s}k{\i}n and Ekim, Tinaz} } @article {ekim2010recognizing, title = {Recognizing line-polar bipartite graphs in time O (n)}, journal = {Discrete Applied Mathematics}, volume = {158}, number = {15}, year = {2010}, pages = {1593{\textendash}1598}, publisher = {Elsevier}, author = {Ekim, Tinaz and Huang, Jing} } @article {ekim2010split, title = {Split-critical and uniquely split-colorable graphs}, journal = {Discrete Mathematics and Theoretical Computer Science}, volume = {12}, number = {5}, year = {2010}, pages = {1{\textendash}24}, author = {Ekim, Tinaz and Ries, Bernard and de Werra, Dominique and others} } @article {ekim2009partitioning, title = {Partitioning graphs into complete and empty graphs}, journal = {Discrete Mathematics}, volume = {309}, number = {19}, year = {2009}, pages = {5849{\textendash}5856}, publisher = {Elsevier}, author = {Ekim, Tinaz and Gimbel, John} } @article {demange2009tutorial, title = {A tutorial on the use of graph coloring for some problems in robotics}, journal = {European Journal of Operational Research}, volume = {192}, number = {1}, year = {2009}, pages = {41{\textendash}55}, publisher = {North-Holland}, author = {Demange, Marc and Ekim, Tinaz and de Werra, Dominique} } @article {geinoz2008construction, title = {Construction of balanced sports schedules using partitions into subleagues}, journal = {Operations Research Letters}, volume = {36}, number = {3}, year = {2008}, pages = {279{\textendash}282}, publisher = {North-Holland}, author = {Geinoz, A and Ekim, Tinaz and de Werra, Dominique} } @article {demange2008minimum, title = {Minimum maximal matching is NP-hard in regular bipartite graphs}, journal = {Theory and Applications of Models of Computation}, year = {2008}, pages = {364{\textendash}374}, publisher = {Springer}, author = {Demange, Marc and Ekim, Tinaz} } @article {ekim2008polar, title = {Polar cographs}, journal = {Discrete Applied Mathematics}, volume = {156}, number = {10}, year = {2008}, pages = {1652{\textendash}1660}, publisher = {North-Holland}, author = {Ekim, Tinaz and Mahadev, Nadimpalli VR and de Werra, Dominique} } @article {ekim2008polarity, title = {Polarity of chordal graphs}, journal = {Discrete Applied Mathematics}, volume = {156}, number = {13}, year = {2008}, pages = {2469{\textendash}2479}, publisher = {Elsevier}, author = {Ekim, Tinaz and Hell, Pavol and Stacho, Juraj and de Werra, Dominique} } @article {demange2006approximation, title = {On the approximation of Min Split-coloring and Min Cocoloring.}, journal = {J. Graph Algorithms Appl.}, volume = {10}, number = {2}, year = {2006}, pages = {297{\textendash}315}, author = {Demange, Marc and Ekim, Tinaz and de Werra, Dominique and others} } @article {de2006construction, title = {Construction of sports schedules with multiple venues}, journal = {Discrete Applied Mathematics}, volume = {154}, number = {1}, year = {2006}, pages = {47{\textendash}58}, publisher = {North-Holland}, author = {de Werra, Dominique and Ekim, Tinaz and Raess, C} } @article {ekim2006split, title = {On split-coloring problems (vol 10, pg 211, 2005)}, journal = {JOURNAL OF COMBINATORIAL OPTIMIZATION}, volume = {11}, number = {1}, year = {2006}, pages = {125{\textendash}125}, publisher = {SPRINGER VAN GODEWIJCKSTRAAT 30, 3311 GZ DORDRECHT, NETHERLANDS}, author = {Ekim, Tinaz and de Werra, Dominique} } @article {demange2005p, title = {(p, k)-coloring problems in line graphs}, journal = {Theoretical computer science}, volume = {349}, number = {3}, year = {2005}, pages = {462{\textendash}474}, publisher = {Elsevier}, author = {Demange, Marc and Ekim, Tinaz and de Werra, Dominique} } @article {demange2005partitioning, title = {Partitioning cographs into cliques and stable sets}, journal = {Discrete Optimization}, volume = {2}, number = {2}, year = {2005}, pages = {145{\textendash}153}, publisher = {Elsevier}, author = {Demange, Marc and Ekim, Tinaz and de Werra, Dominique} } @article {ekim2005split, title = {On split-coloring problems}, journal = {Journal of Combinatorial Optimization}, volume = {10}, number = {3}, year = {2005}, pages = {211{\textendash}225}, publisher = {Kluwer Academic Publishers}, author = {Ekim, Tinaz and de Werra, Dominique} } @article {ekim2004approximation, title = {Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa}, journal = {International Journal of Computer Mathematics}, volume = {81}, number = {5}, year = {2004}, pages = {569{\textendash}582}, publisher = {Taylor \& Francis Group}, author = {Ekim, Tinaz and Paschos, Vangelis Th} }