Threshold-coloring and unit-cube contact representation of planar graphs

DOI10.1016/J.DAM.2015.09.003MaRDI QIDQ344821zbMATH OpenOpenAlexFDO

Authors Md. Jawaherul Alam, Steven Chaplick, Gašper Fijavž, Michael Kaufmann, Stephen G. Kobourov, Sergey Pupyrev, Jackson Toeniskoetter

Publication date 24 November 2016

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

Full work available at URL https://doi.org/10.1016/j.dam.2015.09.003

zbMATH Keywords

graph coloringplanar graphsthreshold coloringunit-cube contact representation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Threshold-coloring and unit-cube contact representation of graphs
• On representing graphs by touching cuboids
• Contact representations of planar graphs with cubes
• On Contact Graphs with Cubes and Proportional Boxes
• Weak unit disk and interval representation of graphs

Cites work

• scientific article; zbMATH DE number 867661 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A linear-time algorithm for proper interval graph recognition
• An unexpected result in coding the vertices of a graph
• Colouring the real line
• Contact representations of planar graphs with cubes
• Difference graphs
• Distance Graphs on the Integers
• Distance labeling in graphs (extended abstract)
• Exact algorithms for \(L(2,1)\)-labeling of graphs
• Fixed-parameter complexity of \(\lambda\)-labelings
• Fun with algorithms. 7th international conference, FUN 2014, Lipari Island, Sicily, Italy, July 1--3, 2014. Proceedings
• Graph Classes: A Survey
• Graph Sandwich Problems
• Integral mixed unit interval graphs
• Interval representations of planar graphs
• Labelling Graphs with a Condition at Distance 2
• On representing graphs by touching cuboids
• On the complexity of DNA physical mapping
• Simple linear time recognition of unit interval graphs
• Systems of distant representatives
• Threshold graphs and related topics
• Threshold-coloring and unit-cube contact representation of graphs
• Weak unit disk and interval representation of graphs

Cited in

(4)

• The maximal clique and colourability of curve contact graphs
• Threshold-coloring and unit-cube contact representation of graphs
• Weak unit disk and interval representation of graphs
• On representing graphs by touching cuboids

This page was built for publication: Threshold-coloring and unit-cube contact representation of planar graphs

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