Mock threshold graphs

DOI10.1016/J.DISC.2018.04.023MaRDI QIDQ1637131zbMATH OpenOpenAlexWikidataFDO

Authors Richard Behr, Vaidy Sivaraman, Thomas Zaslavsky

Publication date 7 June 2018

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.06622

zbMATH Keywords

chordal graphclaw-free graphforbidden induced subgraphline graphmock threshold graphperfect graph

Mathematics Subject Classification ID

Perfect graphs (05C17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph operations (line graphs, products, etc.) (05C76)

Abstract: Mock threshold graphs are a simple generalization of threshold graphs that, like threshold graphs, are perfect graphs. Our main theorem is a characterization of mock threshold graphs by forbidden induced subgraphs. Other theorems characterize mock threshold graphs that are claw-free and that are line graphs. We also discuss relations with chordality and well-quasi-ordering as well as algorithmic aspects.

Recommendations

• Threshold graphs
• Threshold tolerance graphs
• Near threshold graphs
• Threshold graphs and related topics
• Multithreshold graphs
• Quasi-threshold graphs
• Paired threshold graphs
• Weakly threshold graphs
• Random threshold graphs
• Threshold Channel Graphs

Cites work

• A characterization of perfect graphs
• Characterizations of derived graphs
• Claw-free graphs---a survey
• Complexity Results for Bandwidth Minimization
• Hamiltonian threshold graphs
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• Improved algorithms for weakly chordal graphs
• On rigid circuit graphs
• Quasi-threshold graphs
• The strong perfect graph theorem
• Threshold graphs and related topics
• Upper bounds to the clique width of graphs
• Weakly triangulated graphs

Cited in

(5)

• On total coloring of some classes of regular graphs
• Forbidden induced subgraphs
• scientific article; zbMATH DE number 1161290 (Why is no real title available?)
• Linear-time recognition of double-threshold graphs
• Hereditary Nordhaus-Gaddum graphs

This page was built for publication: Mock threshold graphs

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