A characterization of 2-tree proper interval 3-graphs

DOI10.1155/2014/143809MaRDI QIDQ2249945zbMATH OpenOpenAlexWikidataFDO

Authors David E. Brown, Breeann M. Flesch

Publication date 4 July 2014

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

Full work available at URL https://doi.org/10.1155/2014/143809

zbMATH Keywords

forbidden induced subgraphsinterval \(p\)-graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76)

Review text

Summary: An interval \(p\)-graph is the intersection graph of a collection of intervals which have been colored with \(p\) different colors with edges corresponding to nonempty intersection of intervals from different color classes. We characterize the class of 2-trees which are interval 3-graphs via a list of three graphs and three infinite families of forbidden induced subgraphs.

Recommendations

• A characterization of 2-tree probe interval graphs
• A characterization of k-trees that are interval p-graphs
• Interval Graphs with Containment Restrictions
• A new characterization of proper interval graphs
• Pseudo‐Interval Graphs

Cites work

• A characterization of 2-tree proper interval 3-graphs
• A characterization of k-trees that are interval p-graphs
• Adjacency matrices of probe interval graphs
• Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
• Characterizations for unit interval bigraphs
• scientific article; zbMATH DE number 4132187 (Why is no real title available?)
• scientific article; zbMATH DE number 3815694 (Why is no real title available?)
• scientific article; zbMATH DE number 1735726 (Why is no real title available?)
• scientific article; zbMATH DE number 1933220 (Why is no real title available?)
• scientific article; zbMATH DE number 1743762 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• Indifference Digraphs: A Generalization of Indifference Graphs and Semiorders
• Interval bigraphs and circular arc graphs
• Interval digraphs: An analogue of interval graphs
• Obstacle numbers of graphs
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Weakly triangulated graphs

Cited in

(8)

• Interval \(k\)-graphs and orders
• A characterization of 2-tree proper interval 3-graphs
• A characterization of 2-tree probe interval graphs
• Improper interval graphs and the corresponding minimal forbidden interval subgraphs
• A characterization of k-trees that are interval p-graphs
• Stability of critical p-improper interval graphs
• Metric characterizations of proper interval graphs and tree-clique graphs
• Asteroidal-triple-free interval \(k\)-graphs

This page was built for publication: A characterization of 2-tree proper interval 3-graphs

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