On the structure of graphs with few \(P_4\)s

DOI10.1016/S0166-218X(97)90120-7zbMath0908.05065MaRDI QIDQ1392556

Stephan Olariu, Luitpold Babel

Publication date: 18 October 1998

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

isomorphism problembrittlecograph\(P_4\)

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (32)

The micro-world of cographs ⋮ On the geodetic hull number of \(P_{k}\)-free graphs ⋮ Geodetic Convexity Parameters for Graphs with Few Short Induced Paths ⋮ The A4-structure of a graph ⋮ Some links between identifying codes and separating, dominating and total dominating sets in graphs ⋮ Total dominating sequences in trees, split graphs, and under modular decomposition ⋮ A de Bruijn-Erdős theorem for \((q,q-4)\)-graphs ⋮ Spy game: FPT-algorithm, hardness and graph products ⋮ Locally identifying coloring of graphs with few P4s ⋮ On the \(b\)-coloring of \(P_{4}\)-tidy graphs ⋮ Spy game: FPT-algorithm and results on graph products ⋮ Counting spanning trees using modular decomposition ⋮ Fixed-parameter algorithms for the cocoloring problem ⋮ Clique-width of partner-limited graphs ⋮ Recognition and isomorphism of tree-like \(P_4\)-connected graphs ⋮ Hardness and inapproximability of convex recoloring problems ⋮ 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 ⋮ \(L(2, 1)\)-labelling of graphs with few \(P_4\)'s ⋮ \(2K_2\)-partition of some classes of graphs ⋮ Unnamed Item ⋮ Geodetic convexity parameters for \((q, q - 4)\)-graphs ⋮ Counting Spanning Trees in Graphs Using Modular Decomposition ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ The Maximum Time of 2-neighbour Bootstrap Percolation in Grid Graphs and Parametrized Results ⋮ Triangulating graphs with few \(P_4\)'s ⋮ Restricted coloring problems on graphs with few ⋮ Laplacian integrality in \(P_4\)-sparse and \(P_4\)-extendible graphs ⋮ Grundy dominating sequences on \(X\)-join product ⋮ ON GRAPHS WITH LIMITED NUMBER OF P₄-PARTNERS ⋮ ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complement reducible graphs
• On a unique tree representation for \(P_ 4\)-extendible graphs
• A tree representation for \(P_ 4\)-sparse graphs
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• A New Class of Brittle Graphs
• A Linear Recognition Algorithm for Cographs
• The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
• Isomorphism Testing in Hookup Classes
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• P-Components and the Homogeneous Decomposition of Graphs

This page was built for publication: On the structure of graphs with few \(P_4\)s