Boxicity of graphs on surfaces

DOI10.1007/S00373-012-1130-XMaRDI QIDQ2376090zbMATH OpenOpenAlexFDO

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

acyclic coloringboxicitygraphs on surfacesminor-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

• 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
• 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?)
• 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

(17)

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

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)