Polarity of chordal graphs

DOI10.1016/j.dam.2008.01.026zbMath1163.05051OpenAlexW2007560929MaRDI QIDQ955313

Pavol Hell, Juraj Stacho, Dominique de Werra, Tınaz Ekim

Publication date: 19 November 2008

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

Full work available at URL: https://doi.org/10.1016/j.dam.2008.01.026

zbMATH Keywords

polar graphpolynomial algorithmchordal graphgraph grammarmonopolar graphforbidden subgraph characterizationmatrix partitiongeneralized colouringminimal obstruction

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Related Items

Monopolar graphs: complexity of computing classical graph parameters, Recognizing line-polar bipartite graphs in time \(O(n)\), Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs, List monopolar partitions of claw-free graphs, Complexity and algorithms for recognizing polar and monopolar graphs, On the Polarity and Monopolarity of Graphs, A forbidden subgraph characterization of line-polar bipartite graphs, Minimal obstructions to \(( \infty , k )\)-polarity in cographs, Graph partitions with prescribed patterns, On \(P_4\)-transversals of chordal graphs, Join colourings of chordal graphs, On Injective Colourings of Chordal Graphs, Algorithms for unipolar and generalized split graphs, Minimal obstructions for a matrix partition problem in chordal graphs, Partitioning a graph into disjoint cliques and a triangle-free graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• List matrix partitions of chordal graphs
• About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs
• Partitioning chordal graphs into independent sets and cliques
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
• Matrix partitions of perfect graphs
• Complexity of graph partition problems
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• On generalized graph colorings
• Handbook of Graph Grammars and Computing by Graph Transformation
• On Injective Colourings of Chordal Graphs
• Depth-First Search and Linear Graph Algorithms
• Polar cographs