Dominating subgraphs in graphs with some forbidden structures (Q1343259)

Let \(G= G(V,E)\) be a simple finite graph without isolated vertices, \(P_ i\) a path with \(i\) vertices, and \(C_ i\) a cycle with \(i\) vertices. A set \(D\subseteq V(G)\) is a dominating set of \(G\) if, for any vertex \(v\) in \(V(G)\) but not in \(D\), there is a vertex \(u\) in \(D\) such that \(uv\) is an edge. \(D\) is said to dominate \(G\). A subgraph \(H\) of \(G\) is a dominating subgraph of \(G\) if \(V(H)\) dominates \(G\). \(G\) is said to be \(H\)-free if \(G\) has no induced subgraph which is isomorphic to \(H\). In the literature, for several classes of graphs \(\psi\), the classes \(G(\psi)\) of graphs with the property that all connected induced subgraphs of \(G\in G(\psi)\) have a dominating induced subgraph in \(\psi\), were characterized by so-called forbidden structures. In the present paper, the authors prove statements for the class of triangle-free graphs \(G\) in analogy to the Baćso-Tuza theorem, namely: (1) A graph \(G\) is both \(P_ 6\)-free and \(C_ 6\)-free iff every connected induced subgraph of \(G\) has a dominating complete bipartite subgraph (Theorem 1); and in a much stronger form: (2) \(G\) is \(P_ 6\)-free iff every connected induced subgraph of \(G\) has a dominating complete bipartite subgraph or a dominating induced \(C_ 6\) (Theorem 2). In the case where the graph \(G\) may contain triangles, the results are the following ones: (3) If \(G\) is a connected, \(P_ 6\)-free and \(C_ 6\)-free graph, then it has a dominating subgraph \(H\) which contains a dominating edge (Theorem 3); (4) A connected graph \(G\) is \(P_ 6\)-free iff each connected induced subgraph has a dominating clique or a dominating induced \(C_ 5\) (Theorem 4). Using a known theorem, from these results follows that a triangle-free graph is 3-colourable if every connected induced subgraph has an induced dominating bipartite subgraph.