Separation dimension of graphs and hypergraphs

DOI10.1007/s00453-015-0050-6zbMath1345.05067OpenAlexW1660733406MaRDI QIDQ300474

Martin Charles Golumbic, Manu Basavaraju, Rogers Mathew, Deepak Rajendraprasad, L. Sunil Chandran

Publication date: 28 June 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-015-0050-6

zbMATH Keywords

line graphacyclic chromatic numberboxicityscrambling permutationseparation dimension

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph operations (line graphs, products, etc.) (05C76)

Related Items

Induced Separation Dimension, Local boxicity and maximum degree, Fractional and circular separation dimension of graphs, The induced separation dimension of a graph, Separation dimension and degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Boxicity of line graphs
• Dimensions of hypergraphs
• Interval representations of planar graphs
• The book thickness of a graph
• On acyclic colorings of planar graphs
• The maximum number of edges in a graph of bounded dimension, with applications to ring theory
• A special planar satisfiability problem and a consequence of its NP- completeness
• On the order dimension of 1-sets versus \(k\)-sets
• On acyclic colorings of graphs on surfaces
• Boxicity of graphs on surfaces
• Boxicity of series-parallel graphs
• Boxicity and treewidth
• Separation Dimension of Bounded Degree Graphs
• Extremal graphs of order dimension 4
• A note on scrambling permutations
• Scrambling permutations and entropy of hypergraphs
• Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
• Sequence Covering Arrays
• Minimal scrambling sets of simple orders
• Concerning a Certain Set of Arrangements
• Boxicity and Poset Dimension