A new characterization of P_k-free graphs
From MaRDI portal
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Paths and cycles (05C38) Connectivity (05C40) Structural characterization of families of graphs (05C75)
Recommendations
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- A New Characterization of P 6-Free Graphs
- A new characterization of \(P_{6}\)-free graphs
- Characterization of \(P_{6}\)-free graphs
- Complement reducible graphs
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Dominating cliques in \(P_ 5\)-free graphs
- Dominating cliques in graphs
- Dominating subgraphs in graphs with some forbidden structures
- Improved complexity results on \(k\)-coloring \(P _{t }\)-free graphs
- Independent set in \(P_5\)-free graphs in polynomial time
- The price of connectivity for dominating set: upper bounds and complexity
- Three complexity results on coloring \(P_k\)-free graphs
Cited in
(25)- Characterization of \(P_{6}\)-free graphs
- The maximum size of an edge 2-neighborhood in \(P_5\)-free graphs
- On the computational complexity of the bipartizing matching problem
- A new characterization of unichord-free graphs
- Exact and parameterized algorithms for the independent cutset problem
- Vertex cover at distance on \(H\)-free graphs
- On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs
- Complexity of \(C_k\)-coloring in hereditary classes of graphs
- Near-bipartiteness, connected near-bipartiteness, independent feedback vertex set and acyclic vertex cover on graphs having small dominating sets
- Obstructions for three-coloring and list three-coloring \(H\)-free graphs
- Forbidden subgraphs restricting vertices of degree two in a spanning tree
- Level and pseudo-Gorenstein binomial edge ideals
- A New Characterization of P 6-Free Graphs
- Induced disjoint paths and connected subgraphs for \(H\)-free graphs
- Induced disjoint paths and connected subgraphs for \(H\)-free graphs
- Finding matching cuts in \(H\)-free graphs
- Classifying \(k\)-edge colouring for \(H\)-free graphs
- A proof of a conjecture on the connected domination number
- Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time
- scientific article; zbMATH DE number 7525468 (Why is no real title available?)
- Structural domination and coloring of some \(( P_7 , C_7)\)-free graphs
- Connected vertex cover for \((sP_1+P_5)\)-free graphs
- Binomial edge ideals of regularity 3
- A new characterization of \(P_{6}\)-free graphs
- A New Characterization of $$P_k$$-free Graphs
This page was built for publication: A new characterization of \(P_k\)-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q300476)
