Efficient algorithms for graphs with few \(P_4\)'s

DOI10.1016/S0012-365X(00)00258-2zbMath0980.05045OpenAlexW2062287043MaRDI QIDQ5937917

Stephan Olariu, Dieter Kratsch, Luitpold Babel, Ton Kloks, Haiko Müller, Jan Kratochvíl

Publication date: 18 July 2001

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0012-365x(00)00258-2

zbMATH Keywords

Steiner tree problemNP-complete problemsdominationcoloringHamiltonian circuit problempathwidthvertex ranking

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Constructing a minimum height elimination tree of a tree in linear time ⋮ Locally identifying coloring of graphs with few P4s ⋮ Counting spanning trees using modular decomposition ⋮ Fixed-parameter algorithms for the cocoloring problem ⋮ Maximization coloring problems on graphs with few \(P_4\) ⋮ Restricted coloring problems on graphs with few \(P_4\)'s ⋮ Graphs with few \(P_4\)'s under the convexity of paths of order three ⋮ \(b\)-coloring of tight graphs ⋮ The clique operator on graphs with few \(P_{4}\)'s ⋮ Blocking total dominating sets via edge contractions ⋮ The Maximum Time of 2-neighbour Bootstrap Percolation in Grid Graphs and Parametrized Results ⋮ The clique operator on cographs and serial graphs ⋮ Restricted coloring problems on graphs with few ⋮ Grundy dominating sequences on \(X\)-join product