A new characterization of \(P_k\)-free graphs

DOI10.1007/s00453-015-9989-6zbMath1339.05281OpenAlexW2095269023MaRDI QIDQ300476

Oliver Schaudt, Eglantine Camby

Publication date: 28 June 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-015-9989-6

zbMATH Keywords

computational complexity\(P_k\)-free graphconnected domination

Mathematics Subject Classification ID

Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40)

Related Items

The maximum size of an edge 2-neighborhood in \(P_5\)-free graphs, On the computational complexity of the bipartizing matching problem, Induced disjoint paths and connected subgraphs for \(H\)-free graphs, Complexity of \(C_k\)-coloring in hereditary classes of graphs, Finding matching cuts in \(H\)-free graphs, Induced disjoint paths and connected subgraphs for \(H\)-free graphs, Level and pseudo-Gorenstein binomial edge ideals, Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time, Classifying \(k\)-edge colouring for \(H\)-free graphs, Unnamed Item, Connected vertex cover for \((sP_1+P_5)\)-free graphs, Binomial edge ideals of regularity 3, Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs, On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs, A proof of a conjecture on the connected domination number, Vertex cover at distance on \(H\)-free graphs

Cites Work

• Unnamed Item
• The price of connectivity for dominating set: upper bounds and complexity
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Characterization of \(P_{6}\)-free graphs
• A new characterization of \(P_{6}\)-free graphs
• Complement reducible graphs
• Dominating cliques in \(P_ 5\)-free graphs
• Dominating subgraphs in graphs with some forbidden structures
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Three complexity results on coloring \(P_k\)-free graphs
• Improved Complexity Results on k-Coloring P t -Free Graphs
• A New Characterization of P 6-Free Graphs
• Independent Set in P₅-Free Graphs in Polynomial Time
• Dominating cliques in graphs