Roman Soták
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Roman Soták has a total of 107 co-authors. Here are the top co-authors by number of shared publications:
- Borut Lužar
Faculty of Information Studies, Novo mesto, Slovenia
27 shared publications - Stanislav Jendrol'
Institute of Mathematics, P. J. Šafárik University, Košice, Slovakia
13 shared publications Martina Mockovčiaková
University of West Bohemia, Faculty of Applied Sciences Pilsen Czech Republic
7 shared publications- Martina Mockovčiaková
Faculty of Applied Sciences University of West Bohemia Pilsen Czech Republic
5 shared publications Mária Maceková
5 shared publications- Riste Škrekovski
University of Ljubljana, FMF, Ljubljana, Slovenia
5 shared publications
Latest Publications
- 10 October 2025
- Published by Elsevier in Applied Mathematics and Computation
- Vol. 512
On a new problem about the local irregularity of graphs
- 10 October 2025
- Published by Elsevier in Applied Mathematics and Computation
- Vol. 512
On a new problem about the local irregularity of graphs
- 1 January 2025
- Published by AGH University Press in Opuscula Mathematica
- Vol. 45 (1) , 103-111
Note on robust coloring of planar graphs
We consider the robust chromatic number \(\chi_1(G)\) of planar graphs \(G\) and show that there exists an infinite family of planar graphs \(G\) with \(\chi_1(G) = 3\), thus solving a recent problem of Bacsó et al. from [The robust chromatic number of graphs, Graphs Combin. 40 (2024), #89].- 1 January 2025
- Published by AGH University Press in Opuscula Mathematica
- Vol. 45 (1) , 103-111
Note on robust coloring of planar graphs
We consider the robust chromatic number \(\chi_1(G)\) of planar graphs \(G\) and show that there exists an infinite family of planar graphs \(G\) with \(\chi_1(G) = 3\), thus solving a recent problem of Bacsó et al. from [The robust chromatic number of graphs, Graphs Combin. 40 (2024), #89].- 31 January 2024
- Published by Elsevier in Applied Mathematics and Computation
- Vol. 470
Interval vertex coloring
- 31 January 2024
- Published by Elsevier in Applied Mathematics and Computation
- Vol. 470
Interval vertex coloring
- Open Access
On a problem concerning integer distance graphs
For $D$ being a subset of positive integers, the integer distance graph is the graph $G(D)$, whose vertex set is the set of integers, and edge set is the set of all pairs $uv$ with $|u-v| \in D$. It is known that $χ(G(D)) \leq |D|+1$. This article studies the problem (which is motivated by a conjecture of Zhu): "Is it true that $χ(G(D)) = |D|+1$ implies $ω(G(D)) \geq |D|+1$, where $ω(H)$ is the clique number of $H$?". We give a negative answer to this question, by showing an infinite class of integer distance graphs with $χ(G(D))=|D|+1$ but $ω(G(D))=|D|-1$.Open AccessOn a problem concerning integer distance graphs
For $D$ being a subset of positive integers, the integer distance graph is the graph $G(D)$, whose vertex set is the set of integers, and edge set is the set of all pairs $uv$ with $|u-v| \in D$. It is known that $χ(G(D)) \leq |D|+1$. This article studies the problem (which is motivated by a conjecture of Zhu): "Is it true that $χ(G(D)) = |D|+1$ implies $ω(G(D)) \geq |D|+1$, where $ω(H)$ is the clique number of $H$?". We give a negative answer to this question, by showing an infinite class of integer distance graphs with $χ(G(D))=|D|+1$ but $ω(G(D))=|D|-1$. - 22 November 2023
- Published by Wiley in Journal of Graph Theory
- Vol. 105 (4) , 612-632
Revisiting semistrong edge‐coloring of graphs
A matching in a graph is semistrong if every edge of has an endvertex of degree one in the subgraph induced by the vertices of . A semistrong edge‐coloring of a graph is a proper edge‐coloring in which every color class induces a semistrong matching. In this paper, we continue investigation of properties of semistrong edge‐colorings initiated by Gyárfás and Hubenko. We establish tight upper bounds for general graphs and for graphs with maximum degree 3. We also present bounds about semistrong edge‐coloring which follow from results regarding other, at first sight nonrelated, problems. We conclude the paper with several open problems.
- 22 November 2023
- Published by Wiley in Journal of Graph Theory
- Vol. 105 (4) , 612-632
Revisiting semistrong edge‐coloring of graphs
A matching in a graph is semistrong if every edge of has an endvertex of degree one in the subgraph induced by the vertices of . A semistrong edge‐coloring of a graph is a proper edge‐coloring in which every color class induces a semistrong matching. In this paper, we continue investigation of properties of semistrong edge‐colorings initiated by Gyárfás and Hubenko. We establish tight upper bounds for general graphs and for graphs with maximum degree 3. We also present bounds about semistrong edge‐coloring which follow from results regarding other, at first sight nonrelated, problems. We conclude the paper with several open problems.
- 26 June 2023
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 339, 136-148
Locally irregular edge-coloring of subcubic graphs
- 26 June 2023
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 339, 136-148
Locally irregular edge-coloring of subcubic graphs
- 17 November 2022
- Published by Elsevier in Discrete Mathematics
- Vol. 346 (3)
Light 3-stars in embedded graphs
- 17 November 2022
- Published by Elsevier in Discrete Mathematics
- Vol. 346 (3)
Light 3-stars in embedded graphs
- Open Access
Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods
A {\em conflict-free coloring} of a graph {\em with respect to open} (resp., {\em closed}) {\em neighborhood} is a coloring of vertices such that for every vertex there is a color appearing exactly once in its open (resp., closed) neighborhood. Similarly, a {\em unique-maximum coloring} of a graph {\em with respect to open} (resp., {\em closed}) {\em neighborhood} is a coloring of vertices such that for every vertex the maximum color appearing in its open (resp., closed) neighborhood appears exactly once. There is a vast amount of literature on both notions where the colorings need not be proper, i.e., adjacent vertices are allowed to have the same color. In this paper, we initiate a study of both colorings in the proper settings with the focus given mainly to planar graphs. We establish upper bounds for the number of colors in the class of planar graphs for all considered colorings and provide constructions of planar graphs attaining relatively high values of the corresponding chromatic numbers. As a main result, we prove that every planar graph admits a proper unique-maximum coloring with respect to open neighborhood with at most 10 colors, and give examples of planar graphs needing at least $6$ colors for such a coloring. We also establish tight upper bounds for outerplanar graphs. Finally, we provide several new bounds also for the improper setting of considered colorings.Open AccessProper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods
A {\em conflict-free coloring} of a graph {\em with respect to open} (resp., {\em closed}) {\em neighborhood} is a coloring of vertices such that for every vertex there is a color appearing exactly once in its open (resp., closed) neighborhood. Similarly, a {\em unique-maximum coloring} of a graph {\em with respect to open} (resp., {\em closed}) {\em neighborhood} is a coloring of vertices such that for every vertex the maximum color appearing in its open (resp., closed) neighborhood appears exactly once. There is a vast amount of literature on both notions where the colorings need not be proper, i.e., adjacent vertices are allowed to have the same color. In this paper, we initiate a study of both colorings in the proper settings with the focus given mainly to planar graphs. We establish upper bounds for the number of colors in the class of planar graphs for all considered colorings and provide constructions of planar graphs attaining relatively high values of the corresponding chromatic numbers. As a main result, we prove that every planar graph admits a proper unique-maximum coloring with respect to open neighborhood with at most 10 colors, and give examples of planar graphs needing at least $6$ colors for such a coloring. We also establish tight upper bounds for outerplanar graphs. Finally, we provide several new bounds also for the improper setting of considered colorings. - 7 April 2022
- Published by Wiley in Journal of Graph Theory
- Vol. 101 (3) , 428-454
Structure of edges of embedded graphs with minimum degree two
The weight of an edge is the degree‐sum of its end‐vertices. An edge is an ‐edge if and . In 1955, Kotzig proved that every 3‐connected plane graph contains an edge of weight at most 13. Later, Borodin proved the existence of such an edge in plane graphs with minimum degree at least three. If we consider a graph embedded on a surface with nonpositive Euler characteristic, minimum degree at least three and sufficiently large number of vertices, then the existence of an edge of weight at most 15 can be proved. In this paper we consider graphs with minimum degree two, minimum face degree at least three, embedded on a surface with nonpositive Euler characteristic. We prove that every connected graph with sufficiently large number of vertices, minimum degree two and minimum face degree at least , embedded on a surface with nonpositive Euler characteristic, contains an edge of type , , or if , , or if , or if , if , if , and if . We will also discuss the quality of our results.
- 7 April 2022
- Published by Wiley in Journal of Graph Theory
- Vol. 101 (3) , 428-454
Structure of edges of embedded graphs with minimum degree two
The weight of an edge is the degree‐sum of its end‐vertices. An edge is an ‐edge if and . In 1955, Kotzig proved that every 3‐connected plane graph contains an edge of weight at most 13. Later, Borodin proved the existence of such an edge in plane graphs with minimum degree at least three. If we consider a graph embedded on a surface with nonpositive Euler characteristic, minimum degree at least three and sufficiently large number of vertices, then the existence of an edge of weight at most 15 can be proved. In this paper we consider graphs with minimum degree two, minimum face degree at least three, embedded on a surface with nonpositive Euler characteristic. We prove that every connected graph with sufficiently large number of vertices, minimum degree two and minimum face degree at least , embedded on a surface with nonpositive Euler characteristic, contains an edge of type , , or if , , or if , or if , if , if , and if . We will also discuss the quality of our results.
- 30 January 2022
- Published by Wiley in Journal of Graph Theory
- Vol. 100 (4) , 686-697
Strong edge colorings of graphs and the covers of Kneser graphs
- 30 January 2022
- Published by Wiley in Journal of Graph Theory
- Vol. 100 (4) , 686-697
Strong edge colorings of graphs and the covers of Kneser graphs