Intersection dimension of bipartite graphs

DOI10.1007/978-3-319-06089-7_23MaRDI QIDQ5410653zbMATH OpenOpenAlexFDO

Authors Steven Chaplick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Pavol Hell

Publication date 16 April 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-06089-7_23

zbMATH Keywords

boxicityFerrers dimensionNP-hardnessorthogonal ray graphsegment-ray graphsunit grid intersection graph

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Ferrers dimension of grid intersection graphs
• Grid intersection graphs and boxicity
• Intersection dimensions of graph classes
• Forbidden subgraphs of bigraphs of Ferrers dimension 2
• Grid intersection graphs and order dimension

Cited in

(12)

• Bipartite dimensions and bipartite degrees of graphs
• Intersection dimensions of graph classes
• Intersection numbers of bipartite distance-regular graphs
• Ferrers dimension of grid intersection graphs
• On set intersection representations of graphs
• Testing bipartiteness of geometric intersection graphs
• Proper colorability of segment intersection graphs
• Proper colorability of segment intersection graphs
• Boundedness for proper conflict-free and odd colorings
• Recognition and proper coloring of unit segment intersection graphs
• Grid intersection graphs and order dimension
• On geometric bipartite graphs with asymptotically smallest Zarankiewicz numbers

This page was built for publication: Intersection dimension of bipartite graphs

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