Abstract
Let \(G\) be a connected \(P_k\)-free graph, \(k \ge 4\). We show that \(G\) admits a connected dominating set that induces either a \(P_{k-2}\)-free graph or a graph isomorphic to \(P_{k-2}\). In fact, every minimum connected dominating set of \(G\) has this property. This yields a new characterization for \(P_k\)-free graphs: a graph \(G\) is \(P_k\)-free if and only if each connected induced subgraph of \(G\) has a connected dominating set that induces either a \(P_{k-2}\)-free graph, or a graph isomorphic to \(C_k\). We present an efficient algorithm that, given a connected graph \(G\), computes a connected dominating set \(X\) of \(G\) with the following property: for the minimum \(k\) such that \(G\) is \(P_k\)-free, the subgraph induced by \(X\) is \(P_{k-2}\)-free or isomorphic to \(P_{k-2}\). As an application our results, we prove that Hypergraph 2-Colorability can be solved in polynomial time for hypergraphs whose vertex-hyperedge incidence graphs is \(P_7\)-free.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Recall that for a hypergraph \(H = (V,E)\) we define the bipartite vertex-hyperedge incidence graph as the bipartite graph on the set of vertices \(V \cup E\) with the edges \(vY\) such that \(v \in V, Y \in E\) and \(v \in Y\). In the following, we just say the incidence graph.
References
Bacsó, G., Tuza, Z.: Dominating cliques in \({P}_5\)-free graphs. Period. Math. Hungar. 21, 303–308 (1990)
Broersma, H., Fomin, F.V., Golovach, P.A., Paulusma, D.: Three complexity results on coloring \({P}_k\)-free graphs. Euro. J. Combin. 34, 609–619 (2013)
Camby, E., Schaudt, O.: The price of connectivity for dominating sets: upper bounds and complexity. Discrete Appl. Math. 177, 53–59 (2014)
Corneil, D.G., Lerchs, H., Stewart Burlingham, L.: Complement reducible graphs. Discrete Appl. Math. 3, 163–174 (1981)
Cozzens, M.B., Kelleher, L.L.: Dominating cliques in graphs. Discrete Math. 86, 101–116 (1990)
Garey, M.R., Johnson, D.S.: Computers and Intractability. W.H. Freeman and Co., New York (1979)
Hoáng, C.T., Kaminski, M., Lozin, V.V., Sawada, J., Shu, X.: Deciding \(k\)-colorability of \({P}_5\)-free graphs in polynomial time. Algorithmica 57, 74–81 (2010)
Huang, S.: Improved complexity results on \(k\)-coloring \({P}_t\)-free graphs. In: Proceedings of the MFCS, pp. 551–558 (2013)
Liu, J., Peng, Y., Zhao, C.: Characterization of \({P}_6\)-free graphs. Discrete Appl. Math. 155, 1038–1043 (2007)
Liu, J., Zhou, H.: Dominating subgraphs in graphs with some forbidden structures. Discrete Math. 135, 163–168 (1994)
Lokshtanov, D., Vatshelle, M., Villanger, Y.: Independent set in \({P}_5\)-free graphs in polynomial time. In: Proceedings of the SODA, pp. 570–581 (2014)
Randerath, B., Schiermeyer, I.: 3-Colorability \(\in {\cal P}\) for \({P}_6\)-free graphs. Discrete Appl. Math. 136, 299–313 (2004)
van’t Hof, P., Paulusma, D.: A new characterization of \({P}_6\)-free graphs. In: Proceedings of the COCOON, pp. 415–424 (2008)
van’t Hof, P., Paulusma, D.: A new characterization of \({P}_6\)-free graphs. Discrete Appl. Math. 158, 731–740 (2010)
Acknowledgments
We thank three referees for their careful reading of our paper and the helpful comments.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Camby, E., Schaudt, O. A New Characterization of \(P_k\)-Free Graphs. Algorithmica 75, 205–217 (2016). https://doi.org/10.1007/s00453-015-9989-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-015-9989-6