This page has only limited features, please log in for full access.
University Educator/Researcher
01 January 2003 - 01 July 2020
The quality of the environment as well as public health is convincingly coupled with the functioning of a power subsector. The power subsector plays a pivotal role in the sense that it emerges as the key cross-sectional element for the society’s functioning (production, services, healthcare, education and others). A modern society consists of infrastructure systems that are primarily dependent on continuous electricity supplies. Each and every element of the electric power infrastructure is unique, and thus, its malfunction can disrupt the functioning of an important part of the electric power infrastructure. In conjunction with ensuring the functioning of electric power infrastructure, our attention must be drawn to the resilience issue. As far as the resilience of electric power infrastructure is concerned, it can resist weather-related events ensuring there are no disruptions in continuous electricity supplies. First, in the introductory part, the article presents the legal framework in the Slovak Republic. Second, it describes the current state of the electric power infrastructure of Slovakia. Third, it handles the state of the level of security risk assessment. Later on, in the literature review, besides turning to the issue of resilience assessment, the authors focused on the area of resilience of power engineering. Furthermore, the article scrutinizes resilience assessment in Slovakia, and it briefly examines approaches towards natural threats. In addition, the article demonstrates several approaches towards flood resilience. Having used different methods, the primary concern is to devise a framework for resilience assessment. Therefore, the included case study examines aspects of the proposed framework for resilience assessment. In conclusion, our aim was, in most respects, to outline an innovative methodological framework for increasing the resilience of electricity infrastructure.
Zdenek Dvorak; Nikola Chovancikova; Jozef Bruk; Martin Hromada. Methodological Framework for Resilience Assessment of Electricity Infrastructure in Conditions of Slovak Republic. International Journal of Environmental Research and Public Health 2021, 18, 8286 .
AMA StyleZdenek Dvorak, Nikola Chovancikova, Jozef Bruk, Martin Hromada. Methodological Framework for Resilience Assessment of Electricity Infrastructure in Conditions of Slovak Republic. International Journal of Environmental Research and Public Health. 2021; 18 (16):8286.
Chicago/Turabian StyleZdenek Dvorak; Nikola Chovancikova; Jozef Bruk; Martin Hromada. 2021. "Methodological Framework for Resilience Assessment of Electricity Infrastructure in Conditions of Slovak Republic." International Journal of Environmental Research and Public Health 18, no. 16: 8286.
We give a linear-time algorithm to decide 3-colorability of a triangle-free graph embedded in a fixed surface, and a quadratic-time algorithm to output a 3-coloring in the affirmative case. The algorithms also allow to prescribe the coloring of a bounded number of vertices.
Zdeněk Dvořák; Daniel Král'; Robin Thomas. Three-coloring triangle-free graphs on surfaces VII. A linear-time algorithm. Journal of Combinatorial Theory, Series B 2021, 1 .
AMA StyleZdeněk Dvořák, Daniel Král', Robin Thomas. Three-coloring triangle-free graphs on surfaces VII. A linear-time algorithm. Journal of Combinatorial Theory, Series B. 2021; ():1.
Chicago/Turabian StyleZdeněk Dvořák; Daniel Král'; Robin Thomas. 2021. "Three-coloring triangle-free graphs on surfaces VII. A linear-time algorithm." Journal of Combinatorial Theory, Series B , no. : 1.
The reconfiguration graph Rk(G) for the k-colorings of a graph G has as vertices all possible k-colorings of G and two colorings are adjacent if they differ in the color of exactly one vertex. A result of Bousquet and Perarnau (2016) regarding graphs of bounded degeneracy implies that for a planar graph G with n vertices, R12(G) has diameter at most 6n, and if G is triangle-free, then R8(G) has diameter at most 4n. We use a list coloring technique inspired by results of Thomassen to improve on the number of colors, showing that for a planar graph G with n vertices, R10(G) has diameter at most 8n, and if G is triangle-free, then R7(G) has diameter at most 7n.
Zdeněk Dvořák; Carl Feghali. A Thomassen-type method for planar graph recoloring. European Journal of Combinatorics 2021, 95, 103319 .
AMA StyleZdeněk Dvořák, Carl Feghali. A Thomassen-type method for planar graph recoloring. European Journal of Combinatorics. 2021; 95 ():103319.
Chicago/Turabian StyleZdeněk Dvořák; Carl Feghali. 2021. "A Thomassen-type method for planar graph recoloring." European Journal of Combinatorics 95, no. : 103319.
Microbial metabolite mimicry is a new concept that promises to deliver compounds that have minimal liabilities and enhanced therapeutic effects in a host. In a previous publication, we have shown that microbial metabolites of L-tryptophan, indoles, when chemically altered, yielded potent anti-inflammatory pregnane X Receptor (PXR)-targeting lead compounds, FKK5 and FKK6, targeting intestinal inflammation. Our aim in this study was to further define structure-activity relationships between indole analogs and PXR, we removed the phenyl-sulfonyl group or replaced the pyridyl residue with imidazolopyridyl of FKK6. Our results showed that while removal of the phenyl-sulfonyl group from FKK6 (now called CVK003) shifts agonist activity away from PXR towards the aryl hydrocarbon receptor (AhR), the imidazolopyridyl addition preserves PXR activity in vitro. However, when these compounds are administered to mice, that unlike the parent molecule, FKK6, they exhibit poor induction of PXR target genes in the intestines and the liver. These data suggest that modifications of FKK6 specifically in the pyridyl moiety can result in compounds with weak PXR activity in vivo. These observations are a significant step forward for understanding the structure-activity relationships (SAR) between indole mimics and receptors, PXR and AhR.
Hao Li; Peter Illés; Chamini V. Karunaratne; Lars Ulrik Nordstrøm; Xiaoping Luo; Annie Yang; Yunping Qiu; Irwin J. Kurland; Dana J. Lukin; Weijie Chen; Eva Jiskrová; Kristýna Krasulová; Petra Pečinková; Vera M. DesMarais; Qiang Liu; Joseph M. Albanese; Ashwin Akki; Michael Longo; Breyen Coffin; Vivi Dou; Sridhar Mani; Zdeněk Dvořák. Deciphering structural bases of intestinal and hepatic selectivity in targeting pregnane X receptor with indole-based microbial mimics. Bioorganic Chemistry 2021, 109, 104661 .
AMA StyleHao Li, Peter Illés, Chamini V. Karunaratne, Lars Ulrik Nordstrøm, Xiaoping Luo, Annie Yang, Yunping Qiu, Irwin J. Kurland, Dana J. Lukin, Weijie Chen, Eva Jiskrová, Kristýna Krasulová, Petra Pečinková, Vera M. DesMarais, Qiang Liu, Joseph M. Albanese, Ashwin Akki, Michael Longo, Breyen Coffin, Vivi Dou, Sridhar Mani, Zdeněk Dvořák. Deciphering structural bases of intestinal and hepatic selectivity in targeting pregnane X receptor with indole-based microbial mimics. Bioorganic Chemistry. 2021; 109 ():104661.
Chicago/Turabian StyleHao Li; Peter Illés; Chamini V. Karunaratne; Lars Ulrik Nordstrøm; Xiaoping Luo; Annie Yang; Yunping Qiu; Irwin J. Kurland; Dana J. Lukin; Weijie Chen; Eva Jiskrová; Kristýna Krasulová; Petra Pečinková; Vera M. DesMarais; Qiang Liu; Joseph M. Albanese; Ashwin Akki; Michael Longo; Breyen Coffin; Vivi Dou; Sridhar Mani; Zdeněk Dvořák. 2021. "Deciphering structural bases of intestinal and hepatic selectivity in targeting pregnane X receptor with indole-based microbial mimics." Bioorganic Chemistry 109, no. : 104661.
The article discusses the results of research in the field of critical infrastructure protection. The resilience research is aimed at creating a framework for the assessment of static resilience. The complexity of the solution should be given by the framework, which derives from the pillars of safety. The aim is to create technical prerequisites for a possible dynamic assessment of the resilience of critical infrastructure facilities.
Nikola Chovančíková; Zdeněk Dvořák; Bohuš Leitner. Safety indicators as a basis for increasing the resilience of critical infrastructure. Haditechnika 2021, 55, 25 -30.
AMA StyleNikola Chovančíková, Zdeněk Dvořák, Bohuš Leitner. Safety indicators as a basis for increasing the resilience of critical infrastructure. Haditechnika. 2021; 55 (3):25-30.
Chicago/Turabian StyleNikola Chovančíková; Zdeněk Dvořák; Bohuš Leitner. 2021. "Safety indicators as a basis for increasing the resilience of critical infrastructure." Haditechnika 55, no. 3: 25-30.
Plummer and Toft conjectured in 1987 that the vertices of every 3-connected plane graph with maximum face size Δ⋆ can be colored using at most Δ⋆+2 colors in such a way that no face is incident with two vertices of the same color. The conjecture has been proven for Δ⋆=3, Δ⋆=4 and Δ⋆≥18. We prove the conjecture for Δ⋆=16 and Δ⋆=17.
Zdeněk Dvořák; Michael Hebdige; Filip Hlásek; Daniel Král’; Jonathan A. Noel. Cyclic coloring of plane graphs with maximum face size 16 and 17. European Journal of Combinatorics 2020, 94, 103287 .
AMA StyleZdeněk Dvořák, Michael Hebdige, Filip Hlásek, Daniel Král’, Jonathan A. Noel. Cyclic coloring of plane graphs with maximum face size 16 and 17. European Journal of Combinatorics. 2020; 94 ():103287.
Chicago/Turabian StyleZdeněk Dvořák; Michael Hebdige; Filip Hlásek; Daniel Král’; Jonathan A. Noel. 2020. "Cyclic coloring of plane graphs with maximum face size 16 and 17." European Journal of Combinatorics 94, no. : 103287.
For a hereditary class G of graphs, let sG(n) be the minimum function such that each n-vertex graph in G has a balanced separator of order at most sG(n), and let ∇G(r) be the minimum function bounding the expansion of G, in the sense of bounded expansion theory of Nešetřil and Ossona de Mendez. The results of Plotkin et al. (1994) and Esperet and Raymond (2018) imply that if sG(n)=Θ(n1−ε) for some ε>0, then ∇G(r)=Ω(r12ε−1∕polylog r) and ∇G(r)=O(r1ε−1polylog r). Answering a question of Esperet and Raymond, we show that neither of the exponents can be substantially improved.
Zdeněk Dvořák. A note on sublinear separators and expansion. European Journal of Combinatorics 2020, 93, 103273 .
AMA StyleZdeněk Dvořák. A note on sublinear separators and expansion. European Journal of Combinatorics. 2020; 93 ():103273.
Chicago/Turabian StyleZdeněk Dvořák. 2020. "A note on sublinear separators and expansion." European Journal of Combinatorics 93, no. : 103273.
Let G be a simple connected plane graph and let C1 and C2 be cycles in G bounding distinct faces f1 and f2. For a positive integer ℓ, let r(ℓ) denote the number of integers n such that −ℓ≤n≤ℓ, n is divisible by 3, and n has the same parity as ℓ; in particular, r(4)=1. Let rf1,f2(G)=∏fr(|f|), where the product is over the faces f of G distinct from f1 and f2, and let q(G)=1+∑f:|f|≠4|f|, where the sum is over all faces f of G (of length other than four). We give an algorithm with time complexity O(rf1,f2(G)q(G)|G|) which, given a 3-coloring ψ of C1∪C2, either finds an extension of ψ to a 3-coloring of G, or correctly decides no such extension exists. The algorithm is based on a min–max theorem for a variant of integer 2-commodity flows, and consequently in the negative case produces an obstruction to the existence of the extension. As a corollary, we show that every triangle-free graph drawn in the torus with edge-width at least 21 is 3-colorable.
Zdeněk Dvořák; Jakub Pekárek. Coloring near-quadrangulations of the cylinder and the torus. European Journal of Combinatorics 2020, 93, 103258 .
AMA StyleZdeněk Dvořák, Jakub Pekárek. Coloring near-quadrangulations of the cylinder and the torus. European Journal of Combinatorics. 2020; 93 ():103258.
Chicago/Turabian StyleZdeněk Dvořák; Jakub Pekárek. 2020. "Coloring near-quadrangulations of the cylinder and the torus." European Journal of Combinatorics 93, no. : 103258.
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 ( g 1 ∕ 4 log g ) as g → ∞ . This is sharp up to the logarithmic factor.
Zdeněk Dvořák; Louis Esperet; Ross J. Kang; Kenta Ozeki. Single‐conflict colouring. Journal of Graph Theory 2020, 97, 148 -160.
AMA StyleZdeněk Dvořák, Louis Esperet, Ross J. Kang, Kenta Ozeki. Single‐conflict colouring. Journal of Graph Theory. 2020; 97 (1):148-160.
Chicago/Turabian StyleZdeněk Dvořák; Louis Esperet; Ross J. Kang; Kenta Ozeki. 2020. "Single‐conflict colouring." Journal of Graph Theory 97, no. 1: 148-160.
Let G be a planar graph with a list assignment L . Suppose a preferred color is given for some of the vertices. We prove that if G is triangle‐free and all lists have size at least four, then there exists an L ‐coloring respecting at least a constant fraction of the preferences.
Zdeněk Dvořák; Tomáš Masařík; Jan Musílek; Ondřej Pangrác. Flexibility of triangle‐free planar graphs. Journal of Graph Theory 2020, 96, 619 -641.
AMA StyleZdeněk Dvořák, Tomáš Masařík, Jan Musílek, Ondřej Pangrác. Flexibility of triangle‐free planar graphs. Journal of Graph Theory. 2020; 96 (4):619-641.
Chicago/Turabian StyleZdeněk Dvořák; Tomáš Masařík; Jan Musílek; Ondřej Pangrác. 2020. "Flexibility of triangle‐free planar graphs." Journal of Graph Theory 96, no. 4: 619-641.
Significant attrition limits drug discovery. The available chemical entities present with drug-like features contribute to this limitation. Using specific examples of promiscuous receptor-ligand interactions, a case is made for expanding the chemical space for drug-like molecules. These ligand-receptor interactions are poor candidates for the drug discovery process. However, provided herein are specific examples of ligand-receptor or transcription-factor interactions, namely, the pregnane X receptor (PXR) and the aryl hydrocarbon receptor (AhR), and its interactions with microbial metabolites. Discrete examples of microbial metabolite mimicry are shown to yield more potent and non-toxic therapeutic leads for pathophysiological conditions regulated by PXR and AhR. These examples underscore the opinion that microbial metabolite mimicry of promiscuous ligand-receptor interactions is warranted, and will likely expand the existing chemical space of drugs.
Zdeněk Dvořák; Harry Sokol; Sridhar Mani. Drug Mimicry: Promiscuous Receptors PXR and AhR, and Microbial Metabolite Interactions in the Intestine. Trends in Pharmacological Sciences 2020, 41, 900 -908.
AMA StyleZdeněk Dvořák, Harry Sokol, Sridhar Mani. Drug Mimicry: Promiscuous Receptors PXR and AhR, and Microbial Metabolite Interactions in the Intestine. Trends in Pharmacological Sciences. 2020; 41 (12):900-908.
Chicago/Turabian StyleZdeněk Dvořák; Harry Sokol; Sridhar Mani. 2020. "Drug Mimicry: Promiscuous Receptors PXR and AhR, and Microbial Metabolite Interactions in the Intestine." Trends in Pharmacological Sciences 41, no. 12: 900-908.
Robin Thomas asked whether for every proper minor-closed class G, there exists a polynomial-time algorithm approximating the chromatic number of graphs from G up to a constant additive error independent on the class G. We show this is not the case: unless P=NP, for every integer k≥1, there is no polynomial-time algorithm to color a K4k+1-minor-free graph G using at most χ(G)+k−1 colors. More generally, for every k≥1 and 1≤β≤4/3, there is no polynomial-time algorithm to color a K4k+1-minor-free graph G using less than βχ(G)+(4−3β)k colors. As far as we know, this is the first non-trivial non-approximability result regarding the chromatic number in proper minor-closed classes. Furthermore, we give somewhat weaker non-approximability bound for K4k+1-minor-free graphs with no cliques of size 4. On the positive side, we present additive approximation algorithm whose error depends on the apex number of the forbidden minor, and an algorithm with additive error 6 under the additional assumption that the graph has no 4-cycles.
Zdeněk Dvořák; Ken-Ichi Kawarabayashi. Additive non-approximability of chromatic number in proper minor-closed classes. Journal of Combinatorial Theory, Series B 2020, 1 .
AMA StyleZdeněk Dvořák, Ken-Ichi Kawarabayashi. Additive non-approximability of chromatic number in proper minor-closed classes. Journal of Combinatorial Theory, Series B. 2020; ():1.
Chicago/Turabian StyleZdeněk Dvořák; Ken-Ichi Kawarabayashi. 2020. "Additive non-approximability of chromatic number in proper minor-closed classes." Journal of Combinatorial Theory, Series B , no. : 1.
Let G be a 4-critical graph with t triangles, embedded in a surface of genus g. Let c be the number of 4-cycles in G that do not bound a 2-cell face. We prove that∑fface ofG(|f|−4)≤κ(g+t+c−1) for a fixed constant κ, thus generalizing and strengthening several known results. As a corollary, we prove that every triangle-free graph G embedded in a surface of genus g contains a set of O(g) vertices such that G−X is 3-colorable.
Zdeněk Dvořák; Daniel Král'; Robin Thomas. Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes of 4-critical graphs. Journal of Combinatorial Theory, Series B 2020, 150, 270 -304.
AMA StyleZdeněk Dvořák, Daniel Král', Robin Thomas. Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes of 4-critical graphs. Journal of Combinatorial Theory, Series B. 2020; 150 ():270-304.
Chicago/Turabian StyleZdeněk Dvořák; Daniel Král'; Robin Thomas. 2020. "Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes of 4-critical graphs." Journal of Combinatorial Theory, Series B 150, no. : 270-304.
We give an upper bound on the number of cycles in a simple graph in terms of its degree sequence, and apply this bound to resolve several conjectures of Király (2009) and Arman and Tsaturian (2017) and to improve upper bounds on the maximum number of cycles in a planar graph.
Zdeněk Dvořák; Natasha Morrison; Jonathan A. Noel; Sergey Norin; Luke Postle. Bounding the number of cycles in a graph in terms of its degree sequence. European Journal of Combinatorics 2020, 91, 103206 .
AMA StyleZdeněk Dvořák, Natasha Morrison, Jonathan A. Noel, Sergey Norin, Luke Postle. Bounding the number of cycles in a graph in terms of its degree sequence. European Journal of Combinatorics. 2020; 91 ():103206.
Chicago/Turabian StyleZdeněk Dvořák; Natasha Morrison; Jonathan A. Noel; Sergey Norin; Luke Postle. 2020. "Bounding the number of cycles in a graph in terms of its degree sequence." European Journal of Combinatorics 91, no. : 103206.
The Hall ratio of a graph G is the maximum of |V(H)|/α(H) over all subgraphs H of G. It is easy to see that the Hall ratio of a graph is a lower bound for the fractional chromatic number. It has been asked whether conversely, the fractional chromatic number is upper bounded by a function of the Hall ratio. We answer this question in negative, by showing two results of independent interest regarding 1-subdivisions (the 1-subdivision of a graph is obtained by subdividing each edge exactly once). For every c > 0, every graph of sufficiently large average degree contains as a subgraph the 1-subdivision of a graph of fractional chromatic number at least c. For every d > 0, there exists a graph G of average degree at least d such that every graph whose 1-subdivision appears as a subgraph of G has Hall ratio at most 18. We also discuss the consequences of these results in the context of graph classes with bounded expansion.
Zdenĕk Dvořák; Patrice Ossona De Mendez; Hehui Wu. 1-Subdivisions, the Fractional Chromatic Number and the Hall Ratio. Combinatorica 2020, 40, 759 -774.
AMA StyleZdenĕk Dvořák, Patrice Ossona De Mendez, Hehui Wu. 1-Subdivisions, the Fractional Chromatic Number and the Hall Ratio. Combinatorica. 2020; 40 (6):759-774.
Chicago/Turabian StyleZdenĕk Dvořák; Patrice Ossona De Mendez; Hehui Wu. 2020. "1-Subdivisions, the Fractional Chromatic Number and the Hall Ratio." Combinatorica 40, no. 6: 759-774.
The purpose of this paper is to present the development of a qualitative approach to environmental risk assessment (QAERA) in transport. The approach is described as a model developed for the future software tool which will be utilizable as a risk decision support system. The basic part is aimed on developing a quantitative environmental risk assessment. Thus, this paper describes a set of 6 pillars of safety and security. Accordingly, the paper contains both chosen safety and security indicators and selected criteria for assessing the risk of launching the environmental change of global model thinking in the transport sector. The environmental risk assessment as a global model of thinking was originally based on historical experience but, nowadays, it is changing. Based on new expert knowledge, more precisely, on input of new global data, paper displays an environmental risk assessment with actual interpretation. The discussion of the paper is oriented to support research results, a new knowledge-oriented approach to global climate changes, using suitable risk assessment methods and technics. The result of the paper is a new approach for the modeling of environmental risk assessment in the transport sector.
Zdenek Dvorak; David Rehak; Andrej David; Zoran Cekerevac. Qualitative Approach to Environmental Risk Assessment in Transport. International Journal of Environmental Research and Public Health 2020, 17, 5494 .
AMA StyleZdenek Dvorak, David Rehak, Andrej David, Zoran Cekerevac. Qualitative Approach to Environmental Risk Assessment in Transport. International Journal of Environmental Research and Public Health. 2020; 17 (15):5494.
Chicago/Turabian StyleZdenek Dvorak; David Rehak; Andrej David; Zoran Cekerevac. 2020. "Qualitative Approach to Environmental Risk Assessment in Transport." International Journal of Environmental Research and Public Health 17, no. 15: 5494.
We show that the size of a 4-critical graph of girth at least five is bounded by a linear function of its genus. This strengthens the previous bound on the size of such graphs given by Thomassen. It also serves as the basic case for the description of the structure of 4-critical triangle-free graphs embedded in a fixed surface, presented in a future paper of this series.
Zdeněk Dvořák; Daniel Král'; Robin Thomas. Three-coloring triangle-free graphs on surfaces III. Graphs of girth five. Journal of Combinatorial Theory, Series B 2020, 145, 376 -432.
AMA StyleZdeněk Dvořák, Daniel Král', Robin Thomas. Three-coloring triangle-free graphs on surfaces III. Graphs of girth five. Journal of Combinatorial Theory, Series B. 2020; 145 ():376-432.
Chicago/Turabian StyleZdeněk Dvořák; Daniel Král'; Robin Thomas. 2020. "Three-coloring triangle-free graphs on surfaces III. Graphs of girth five." Journal of Combinatorial Theory, Series B 145, no. : 376-432.
We settle a problem of Havel by showing that there exists an absolute constant d such that if G is a planar graph in which every two distinct triangles are at distance at least d, then G is 3-colorable. In fact, we prove a more general theorem. Let G be a planar graph, and let H be a set of connected subgraphs of G, each of bounded size, such that every two distinct members of H are at least a specified distance apart and all triangles of G are contained in ⋃H. We give a sufficient condition for the existence of a 3-coloring ϕ of G such that for every H∈H the restriction of ϕ to H is constrained in a specified way.
Zdeněk Dvořák; Daniel Král'; Robin Thomas. Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies. Journal of Combinatorial Theory, Series B 2020, 150, 244 -269.
AMA StyleZdeněk Dvořák, Daniel Král', Robin Thomas. Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies. Journal of Combinatorial Theory, Series B. 2020; 150 ():244-269.
Chicago/Turabian StyleZdeněk Dvořák; Daniel Král'; Robin Thomas. 2020. "Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies." Journal of Combinatorial Theory, Series B 150, no. : 244-269.
Let G be a planar graph with a list assignment L. Suppose a preferred color is given for some of the vertices. We prove that if G has girth at least six and all lists have size at least three, then there exists an L‐coloring respecting at least a constant fraction of the preferences.
Zdeněk Dvořák; Tomáš Masařík; Jan Musílek; Ondřej Pangrác. Flexibility of planar graphs of girth at least six. Journal of Graph Theory 2020, 95, 457 -466.
AMA StyleZdeněk Dvořák, Tomáš Masařík, Jan Musílek, Ondřej Pangrác. Flexibility of planar graphs of girth at least six. Journal of Graph Theory. 2020; 95 (3):457-466.
Chicago/Turabian StyleZdeněk Dvořák; Tomáš Masařík; Jan Musílek; Ondřej Pangrác. 2020. "Flexibility of planar graphs of girth at least six." Journal of Graph Theory 95, no. 3: 457-466.
The theory of Dvořák, Král’, and Thomas (Dvořák, 2015) shows that a 4-critical triangle-free graph embedded in the torus has only a bounded number of faces of length greater than 4 and that the size of these faces is also bounded. We study the natural reduction in such embedded graphs—identification of opposite vertices in 4-faces. We give a computer-assisted argument showing that there are exactly four 4-critical triangle-free irreducible toroidal graphs in which this reduction cannot be applied without creating a triangle. Using this result, we show that every 4-critical triangle-free graph embedded in the torus has at most four 5-faces, or a 6-face and two 5-faces, or a 7-face and a 5-face, in addition to at least seven 4-faces. This result serves as a basis for the exact description of 4-critical triangle-free toroidal graphs, which we present in a followup paper.
Zdeněk Dvořák; Jakub Pekárek. Irreducible 4-critical triangle-free toroidal graphs. European Journal of Combinatorics 2020, 88, 103112 .
AMA StyleZdeněk Dvořák, Jakub Pekárek. Irreducible 4-critical triangle-free toroidal graphs. European Journal of Combinatorics. 2020; 88 ():103112.
Chicago/Turabian StyleZdeněk Dvořák; Jakub Pekárek. 2020. "Irreducible 4-critical triangle-free toroidal graphs." European Journal of Combinatorics 88, no. : 103112.