Z2-genus of graphs and minimum rank of partial symmetric matrices

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10398870" target="_blank" >RIV/00216208:11320/19:10398870 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4230/LIPIcs.SoCG.2019.39" target="_blank" >https://doi.org/10.4230/LIPIcs.SoCG.2019.39</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.SoCG.2019.39" target="_blank" >10.4230/LIPIcs.SoCG.2019.39</a>

Result language
angličtina
Original language name
Z2-genus of graphs and minimum rank of partial symmetric matrices
Original language description
The genus g(G) of a graph G is the minimum g such that G has an embedding on the orientable surface M_g of genus g. A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The Z_2-genus of a graph G, denoted by g_0(G), is the minimum g such that G has an independently even drawing on M_g. We prove the following. If G is a union of G_1 and G_2 where G_1 and G_2 intersect in two vertices u and, and G-u-v has k connected components (among which we count the edge uv if present, then |g_0(G)-(g_0(G_1)+g_0(G_2))|<= k+1. For complete bipartite graphs K_{m,n}, with n>= m>= 3, we prove that g_0(K_{m,n})/g(K_{m,n})=1-O(1/n). Similar results are proved also for the Euler genus.
Czech name
—
Czech description
—

Project
<a href="/en/project/GJ19-04113Y" target="_blank" >GJ19-04113Y: Advanced tools in combinatorics, topology and related areas</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Leibniz International Proceedings in Informatics (LIPIcs)
ISBN
978-3-95977-104-7
ISSN
1868-8969
e-ISSN
—
Number of pages
16
Pages from-to
1-16
Publisher name
Schloss Dagstuhl-Leibniz-Zentrum fuer Informati
Place of publication
Dagstuhl
Event location
Portland, Oregon
Event date
Jun 18, 2019
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)