Boxicity of graphs on surfaces

DOI10.1007/S00373-012-1130-XMaRDI QIDQ2376090zbMATHOpenAlexFDO

Authors L. Esperet, Gwenaël Joret

Publication date 26 June 2013

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.1953

zbMATH Keywords

graphs on surfacesacyclic coloringboxicityminor-closed classes

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph minors (05C83)

Abstract: The boxicity of a graph $G=(V,E)$ is the least integer $k$ for which there exist $k$ interval graphs $G_i=(V,E_i)$, $1leilek$, such that $E=E_{1}cap\mathrm{...}cap{E}_k$. Scheinerman proved in 1984 that outerplanar graphs have boxicity at most two and Thomassen proved in 1986 that planar graphs have boxicity at most three. In this note we prove that the boxicity of toroidal graphs is at most 7, and that the boxicity of graphs embeddable in a surface $Sigma$ of genus $g$ is at most $5g+3$. This result yields improved bounds on the dimension of the adjacency poset of graphs on surfaces.

Recommendations

• Boxicity and topological invariants
• Box representations of embedded graphs
• Boxicity of Halin graphs
• An upper bound for cubicity in terms of boxicity
• Boxicity, poset dimension, and excluded minors

Cites work

• scientific article; zbMATH DE number 3737705 (Why is no real title available?)
• scientific article; zbMATH DE number 3566474 (Why is no real title available?)
• scientific article; zbMATH DE number 3307331 (Why is no real title available?)
• scientific article; zbMATH DE number 2209736 (Why is no real title available?)
• A special planar satisfiability problem and a consequence of its NP- completeness
• Adjacency posets of planar graphs
• An extremal function for contractions of graphs
• Boxicity and maximum degree
• Boxicity and treewidth
• Coloring with no 2-colored \(P_4\)'s
• Cubicity, degeneracy, and crossing number
• Dimension, graph and hypergraph coloring
• Graphs on surfaces
• Graphs on the torus and geometry of numbers
• Interval representations of planar graphs
• Lower bound of the Hadwiger number of graphs by their average degree
• Minimal scrambling sets of simple orders
• On acyclic colorings of graphs on surfaces
• Star coloring and acyclic coloring of locally planar graphs

Cited in

(15)

• Boxicity of Halin graphs
• Boxicity of circular arc graphs
• A note on lower bounds for boxicity of graphs
• On the boxicity of Kneser graphs and complements of line graphs
• Local and union boxicity
• Boxicity, poset dimension, and excluded minors
• Poset boxicity of graphs
• Adjacency posets of outerplanar graphs
• Chronological rectangle digraphs which are two-terminal series-parallel
• Better bounds for poset dimension and boxicity
• A note on the intersection property for flat boxes and boxicity in \(\mathbb R^d\)
• On the stab number of rectangle intersection graphs
• Boxicity and topological invariants
• Box representations of embedded graphs
• Separation dimension of graphs and hypergraphs

This page was built for publication: Boxicity of graphs on surfaces

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