The induced separation dimension of a graph

DOI10.1007/S00453-017-0353-XMaRDI QIDQ722529zbMATH OpenOpenAlexFDO

Authors Emile Ziedan, Deepak Rajendraprasad, Rogers Mathew, Martin Charles Golumbic, Jérémie Dusart

Publication date 26 July 2018

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-017-0353-x

zbMATH Keywords

acyclic orientationvertex orderingasteroidal triplesinduced separation dimension

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)

Recommendations

• Induced separation dimension
• Separation dimension and degree
• Fractional and circular separation dimension of graphs
• Separation dimension of bounded degree graphs
• Separation dimension of graphs and hypergraphs

Cites work

• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 2117210 (Why is no real title available?)
• scientific article; zbMATH DE number 3307331 (Why is no real title available?)
• Algorithmic graph theory and perfect graphs
• Boxicity and separation dimension
• Caterpillar tolerance representations
• Coloring edges and vertices of graphs without short or long cycles
• Dimensions of hypergraphs
• Finding a maximum induced matching in weakly chordal graphs
• Graph Classes: A Survey
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• Induced matchings
• Induced matchings in asteroidal triple-free graphs
• Induced matchings in intersection graphs.
• Maximum weight independent sets and cliques in intersection graphs of filaments
• New results on induced matchings
• On toughness and Hamiltonicity of \(2K_{2}\)-free graphs
• Separation dimension of bounded degree graphs
• Separation dimension of graphs and hypergraphs
• Sur le coloriage des graphs
• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
• Tree-decompositions of small pathwidth
• Vertex ordering characterizations of graphs of bounded asteroidal number

Cited in

(3)

• Separation dimension and degree
• Perfect and nearly perfect separation dimension of complete and random graphs
• Induced separation dimension

This page was built for publication: The induced separation dimension of a graph

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