A new characterization of \(P_k\)-free graphs
From MaRDI portal
Publication:300476
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
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 P5-Free Graphs in Polynomial Time
- Dominating cliques in graphs