55 citations · 324 across the 27 of their papers we have counts for
22 papers · 1 filter
List strong and list normal edge-coloring of (sub)cubic graphs
Borut Lužar, Edita Máčajová, Roman Soták +1
A strong edge-coloring of a graph is a proper edge-coloring, in which the edges of every path of length 3 receive distinct colors; in other words, every pair of edges at distance a…
Degree-balanced decompositions of cubic graphs
Borut Lužar, Jakub Przybyło, Roman Soták
We show that every cubic graph on vertices contains a spanning subgraph in which the number of vertices of each degree deviates from by at most , up…
Packing coloring of hypercubes with extended Hamming codes
Petr Gregor, Jaka Kranjc, Borut Lužar +1
A {\em packing coloring} of a graph is a mapping assigning a positive integer (a color) to every vertex of such that every two vertices of color are at distance at leas…
Locally irregular edge-coloring of subcubic graphs
Borut Lužar, Mária Maceková, Simona Rindošová +3
A graph is {\em locally irregular} if no two adjacent vertices have the same degree. A {\em locally irregular edge-coloring} of a graph is such an (improper) edge-coloring that…
Revisiting Semistrong Edge-Coloring of Graphs
Borut Lužar, Martina Mockovčiaková, Roman Soták
A matching in a graph is {\em semistrong} if every edge of has an endvertex of degree one in the subgraph induced by the vertices of . A {\em semistrong edge-colorin…
Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods
Igor Fabrici, Borut Lužar, Simona Rindošová +1
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…
Further Extensions of the Grötzsch Theorem
Hoang La, Borut Lužar, Kenny Štorgel
The Grötzsch Theorem states that every triangle-free planar graph admits a proper -coloring. Among many of its generalizations, the one of Grünbaum and Aksenov, giving -color…
3-facial edge-coloring of plane graphs
Mirko Horňák, Borut Lužar, Kenny Štorgel
An -facial edge-coloring of a plane graph is a coloring of its edges such that any two edges at distance at most on a boundary walk of any face receive distinct colors…
Strong edge colorings of graphs and the covers of Kneser graphs
Borut Lužar, Edita Mačajová, Martin Škoviera +1
A proper edge coloring of a graph is strong if it creates no bichromatic path of length three. It is well known that for a strong edge coloring of a -regular graph at least $2k-…
Star Edge-Coloring of Square Grids
Přemysl Holub, Borut Lužar, Erika Mihaliková +2
A star edge-coloring of a graph is a proper edge-coloring without bichromatic paths or cycles of length four. The smallest integer such that admits a star edge-coloring…
On non-repetitive sequences of arithmetic progressions:the cases
Borut Lužar, Martina Mockovčiaková, Pascal Ochem +2
A -subsequence of a sequence is a subsequence , for any positive integer and any , . A \textit{-Thue seque…
Note on 3-Choosability of Planar Graphs with Maximum Degree 4
François Dross, Borut Lužar, Mária Maceková +1
Deciding whether a planar graph (even of maximum degree ) is -colorable is NP-complete. Determining subclasses of planar graphs being -colorable has a long history, but si…
Note on list star edge-coloring of subcubic graphs
Borut Lužar, Martina Mockovčiaková, Roman Soták
{\emph A star edge-coloring} of a graph is a proper edge-coloring without bichromatic paths and cycles of length four. In this paper, we consider the list version of this coloring…
On facial unique-maximum (edge-)coloring
Vesna Andova, Bernard Lidický, Borut Lužar +1
A facial unique-maximum coloring of a plane graph is a vertex coloring where on each face the maximal color appears exactly once on the vertices of . If the coloring is requ…
New bounds for locally irregular chromatic index of bipartite and subcubic graphs
Borut Lužar, Jakub Przybyło, Roman Soták
A graph is \textit{locally irregular} if the neighbors of every vertex have degrees distinct from the degree of . \textit{locally irregular edge-coloring} of a graph is…
On the difference between the Szeged and Wiener index
Marthe Bonamy, Martin Knor, Borut Lužar +2
We prove a conjecture of Nadjafi-Arani, Khodashenas and Ashrafi on the difference between the Szeged and Wiener index of a graph. Namely, if is a 2-connected non-complete graph…
On incidence coloring conjecture in Cartesian products of graphs
Petr Gregor, Borut Lužar, Roman Soták
An incidence in a graph is a pair where is a vertex of and is an edge of incident to . Two incidences and are adjacent if at least on…
Strong edge coloring of subcubic bipartite graphs
Borut Lužar, Martina Mockovčiaková, Roman Soták +1
A strong edge coloring of a graph is a proper edge coloring in which each color class is an induced matching of . In 1993, Brualdi and Quinn Massey proposed a conjecture tha…
Star edge coloring of some classes of graphs
Ľudmila Bezegová, Borut Lužar, Martina Mockovčiaková +2
\textit{A star edge coloring} of a graph is a proper edge coloring without bichromatic paths and cycles of length four. In this paper we establish tight upper bounds for trees and…
l-facial edge colorings of graphs
Borut Lužar, Martina Mockovčiaková, Roman Soták +2
An l-facial edge coloring of a plane graph is a coloring of the edges such that any two edges at distance at most l on a boundary walk of some face receive distinct colors. It is c…
Strong edge coloring of planar graphs
Dávid Hudák, Borut Lužar, Roman Soták +1
A strong edge coloring of a graph is a proper edge coloring where the edges at distance at most two receive distinct colors. It is known that every planar graph with maximum degree…
A Planar Linear Arboricity Conjecture
Marek Cygan, Lukasz Kowalik, Borut Luzar
The linear arboricity la(G) of a graph G is the minimum number of linear forests that partition the edges of G. In 1984, Akiyama et al. stated the Linear Arboricity Conjecture (LAC…