Single‐conflict colouring Dvořák, Zdeněk; Esperet, Louis; Kang, Ross J. ...
Journal of graph theory,
20/May , Letnik:
97, Številka:
1
Journal Article
Recenzirano
Odprti dostop
Given a multigraph, suppose that each vertex is given a local assignment of k colours to its incident edges. We are interested in whether there is a choice of one local colour per vertex such that no ...edge has both of its local colours chosen. The least k for which this is always possible given any set of local assignments we call the single‐conflict chromatic number of the graph. This parameter is closely related to separation choosability and adaptable choosability. We show that single‐conflict chromatic number of simple graphs embeddable on a surface of Euler genus g is O(g1∕4log g) as g→∞. This is sharp up to the logarithmic factor.
Phase transitions in graphs on orientable surfaces Kang, Mihyun; Moßhammer, Michael; Sprüssel, Philipp
Random structures & algorithms,
July 2020, 2020-07-00, 20200701, Letnik:
56, Številka:
4
Journal Article
Recenzirano
Odprti dostop
Let Sg be the orientable surface of genus g and denote by 𝒮g(n,m) the class of all graphs on vertex set n={1,…,n} with m edges embeddable on Sg. We prove that the component structure of a graph ...chosen uniformly at random from 𝒮g(n,m) features two phase transitions. The first phase transition mirrors the classical phase transition in the Erdős‐Rényi random graph G(n,m) chosen uniformly at random from all graphs with vertex set n and m edges. It takes place at m=n2+O(n2/3), when the giant component emerges. The second phase transition occurs at m=n+O(n3/5), when the giant component covers almost all vertices of the graph. This kind of phenomenon is strikingly different from G(n,m) and has only been observed for graphs on surfaces.
Improved product structure for graphs on surfaces Distel, Marc; Hickingbotham, Robert; Huynh, Tony ...
Discrete mathematics and theoretical computer science,
01/2022, Letnik:
24, no 2, Številka:
Graph Theory
Journal Article
Recenzirano
Odprti dostop
Dujmovi\'c, Joret, Micek, Morin, Ueckerdt and Wood J. ACM 2020 proved that
for every graph $G$ with Euler genus $g$ there is a graph $H$ with treewidth at
most 4 and a path $P$ such that $G\subseteq ...H \boxtimes P \boxtimes
K_{\max\{2g,3\}}$. We improve this result by replacing "4" by "3" and with $H$
planar. We in fact prove a more general result in terms of so-called framed
graphs. This implies that every $(g,d)$-map graph is contained in $ H \boxtimes
P\boxtimes K_\ell$, for some planar graph $H$ with treewidth $3$, where
$\ell=\max\{2g\lfloor \frac{d}{2} \rfloor,d+3\lfloor\frac{d}{2}\rfloor-3\}$. It
also implies that every $(g,1)$-planar graph (that is, graphs that can be drawn
in a surface of Euler genus $g$ with at most one crossing per edge) is
contained in $H\boxtimes P\boxtimes K_{\max\{4g,7\}}$, for some planar graph
$H$ with treewidth $3$.
Celotno besedilo
Dostopno za:
DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, UILJ, UKNU, UL, UM, UPUK
We extend the Marcus–Schaeffer bijection between orientable rooted bipartite quadrangulations (equivalently: rooted maps) and orientable labeled one-face maps to the case of all surfaces, that is ...orientable and non-orientable as well. This general construction requires new ideas and is more delicate than the special orientable case, but it carries the same information. In particular, it leads to a uniform combinatorial interpretation of the counting exponent 5(h−1)2 for both orientable and non-orientable rooted connected maps of Euler characteristic 2−2h, and of the algebraicity of their generating functions, similar to the one previously obtained in the orientable case via the Marcus–Schaeffer bijection. It also shows that the renormalization factor n1/4 for distances between vertices is universal for maps on all surfaces: the renormalized profile and radius in a uniform random pointed bipartite quadrangulation on any fixed surface converge in distribution when the size n tends to infinity. Finally, we extend the Miermont and Ambjørn–Budd bijections to the general setting of all surfaces. Our construction opens the way to the study of Brownian surfaces for any compact 2-dimensional manifold.
We generalize the natural duality of graphs embedded into a surface to a duality with respect to a subset of edges. The dual graph might be embedded into a different surface. We prove a relation ...between the signed Bollobás–Riordan polynomials of dual graphs. This relation unifies various recent results expressing the Jones polynomial of links as specializations of the Bollobás–Riordan polynomials.
Thomassen proved that every planar graph G on n vertices has at least 2n/9 distinct L‐colorings if L is a 5‐list‐assignment for G and at least 2n/10000 distinct L‐colorings if L is a ...3‐list‐assignment for G and G has girth at least five. Postle and Thomas proved that if G is a graph on n vertices embedded on a surface Σ of genus g, then there exist constants ε,cg>0 such that if G has an L‐coloring, then G has at least cg2εn distinct L‐colorings if L is a 5‐list‐assignment for G or if L is a 3‐list‐assignment for G and G has girth at least five. More generally, they proved that there exist constants ε,α>0 such that if G is a graph on n vertices embedded in a surface Σ of fixed genus g, H is a proper subgraph of G, and ϕ is an L‐coloring of H that extends to an L‐coloring of G, then ϕ extends to at least 2ε(n−α(g+|V(H)|)) distinct L‐colorings of G if L is a 5‐list‐assignment or if L is a 3‐list‐assignment and G has girth at least five. We prove the same result if G is triangle‐free and L is a 4‐list‐assignment of G, where ε=18, and α=130.
Let $\mathbb{S}_g$ be the orientable surface of genus $g$ for a fixed non-negative integer $g$. We show that the number of vertex-labelled cubic multigraphs embeddable on $\mathbb{S}_g$ with $2n$ ...vertices is asymptotically $c_g n^{5/2(g-1)-1}\gamma^{2n}(2n)!$, where $\gamma$ is an algebraic constant and $c_g$ is a constant depending only on the genus $g$. We also derive an analogous result for simple cubic graphs and weighted cubic multigraphs. Additionally, for $g\ge1$, we prove that a typical cubic multigraph embeddable on $\mathbb{S}_g$ has exactly one non-planar component.
We outline the progress made so far on the search for the complete set of torus obstructions and also consider practical algorithms for torus embedding and their implementations. We present the set ...of obstructions that are known to-date and give a brief history of how these graphs were found. We also describe a nice algorithm for embedding graphs on the torus which we used to verify previous results and add to the set of torus obstructions. Although it is still exponential in the order of the graph, the algorithm presented here is relatively simple to describe and implement and fast-in-practice for small graphs.It parallels the popular quadratic planar embedding algorithm of Demoucron, Malgrange, and Pertuiset.
PDF
