Strong tree-cographs are Birkhoff graphs

DOI10.1016/0166-218X(88)90100-XzbMATH Open0672.05060OpenAlexW1975000907WikidataQ127564999 ScholiaQ127564999MaRDI QIDQ1119942FDOQ1119942

Authors Gottfried Tinhofer

Publication date 1989

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

Full work available at URL https://doi.org/10.1016/0166-218x(88)90100-x

zbMATH Keywords

isomorphism problemadjacency matricestree-cographsBirkhoff graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Trees (05C05) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Recommendations

• Strong clique trees, neighborhood trees, and strongly chordal graphs
• scientific article; zbMATH DE number 165141
• scientific article; zbMATH DE number 6181702
• On strong tree-breadth
• Tree-core and tree-coritivity of graphs
• The \(k\)-strong induced arboricity of a graph
• scientific article; zbMATH DE number 4093506
• Structural properties of minimal strong digraphs versus trees
• Strong elimination ordering of the total graph of a tree
• Strongly simplicial vertices of powers of trees

Cites work

• scientific article; zbMATH DE number 3920497 (Why is no real title available?)
• scientific article; zbMATH DE number 3481857 (Why is no real title available?)
• scientific article; zbMATH DE number 3545706 (Why is no real title available?)
• scientific article; zbMATH DE number 3575612 (Why is no real title available?)
• scientific article; zbMATH DE number 3383914 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• An Efficient Algorithm for Graph Isomorphism
• Complement reducible graphs
• Graph isomorphism and theorems of Birkhoff type
• Group-theoretic algorithms and graph isomorphism
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• On testing isomorphism of permutation graphs
• On the Assignment Polytope
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(22)

• On some graph classes related to perfect graphs: a survey
• Partial characterizations of circle graphs
• Probe interval and probe unit interval graphs on superclasses of cographs
• Directed path graph isomorphism
• Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
• A note on certain subpolytopes of the assignment polytope associated with circulant graphs
• On Tinhofer's linear programming approach to isomorphism testing
• Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs
• Graph isomorphism, color refinement, and compactness
• Compact cellular algebras and permutation groups
• Classes of graphs for which upper fractional domination equals independence, upper domination, and upper irredundance
• Structure properties of a doubly-stochastic process on a network
• Counting spanning trees in graphs using modular decomposition
• Graph isomorphism and theorems of Birkhoff type
• Isomorphism of chordal (6, 3) graphs
• A note on compact graphs
• Counting spanning trees using modular decomposition
• GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH
• On some special classes of contact \(B_0\)-VPG graphs
• Birkhoff’s theorem for a family of probability spaces
• Acyclic and star colorings of cographs
• On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs

This page was built for publication: Strong tree-cographs are Birkhoff graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1119942)