@article {1499,
	title = {Mind the independence gap},
	journal = {Discrete Mathematics},
	volume = {343},
	year = {2020},
	pages = {111943},
	abstract = {<p>The independence gap of a graph was introduced by Ekim et al.\&nbsp;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.\&nbsp;(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.</p>},
	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 {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 {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 {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 {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}
}
