Source author record

Borut Lužar

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.OC

Catalog footprint

Research overview

11works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

3-facial edge-coloring of plane graphs

An $\ell$ -facial edge-coloring of a plane graph is a coloring of its edges such that any two edges at distance at most $\ell$ on a boundary walk of any face receive distinct colors. It is the edge-coloring variant of the $\ell$ -facial vertex coloring, which arose as a generalization of the well-known cyclic coloring. It is conjectured that at most $3\ell + 1$ colors suffice for an $\ell$ -facial edge-coloring of any plane graph. The conjecture has only been confirmed for $\ell \le 2$ , and in this paper, we prove its validity for $\ell = 3$ .

preprint2021arXiv

BiqBin: a parallel branch-and-bound solver for binary quadratic problems with linear constraints

We present BiqBin, an exact solver for linearly constrained binary quadratic problems. Our approach is based on an exact penalty method to first efficiently transform the original problem into an instance of Max-Cut, and then to solve the Max-Cut problem by a branch-and-bound algorithm. All the main ingredients are carefully developed using new semidefinite programming relaxations obtained by strengthening the existing relaxations with a set of hypermetric inequalities, applying the bundle method as the bounding routine and using new strategies for exploring the branch-and-bound tree. Furthermore, an efficient C implementation of a sequential and a parallel branch-and-bound algorithm is presented. The latter is based on a load coordinator-worker scheme using MPI for multi-node parallelization and is evaluated on a high-performance computer. The new solver is benchmarked against BiqCrunch, GUROBI, and SCIP on four families of (linearly constrained) binary quadratic problems. Numerical results demonstrate that BiqBin is a highly competitive solver. The serial version outperforms the other three solvers on the majority of the benchmark instances. We also evaluate the parallel solver and show that it has good scaling properties. The general audience can use it as an on-line service available at http://www.biqbin.eu.

preprint2021arXiv

Further Extensions of the Grötzsch Theorem

The Grötzsch Theorem states that every triangle-free planar graph admits a proper $3$ -coloring. Among many of its generalizations, the one of Grünbaum and Aksenov, giving $3$ -colorability of planar graphs with at most three triangles, is perhaps the most known. A lot of attention was also given to extending $3$ -colorings of subgraphs to the whole graph. In this paper, we consider $3$ -colorings of planar graphs with at most one triangle. Particularly, we show that precoloring of any two non-adjacent vertices and precoloring of a face of length at most $4$ can be extended to a $3$ -coloring of the graph. Additionally, we show that for every vertex of degree at most $3$ , a precoloring of its neighborhood with the same color extends to a $3$ -coloring of the graph. The latter result implies an affirmative answer to a conjecture on adynamic coloring. All the presented results are tight.

preprint2021arXiv

Strong edge colorings of graphs and the covers of Kneser graphs

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 $k$ -regular graph at least $2k-1$ colors are needed. We show that a $k$ -regular graph admits a strong edge coloring with $2k-1$ colors if and only if it covers the Kneser graph $K(2k-1,k-1)$ . In particular, a cubic graph is strongly $5$ -edge-colorable whenever it covers the Petersen graph. One of the implications of this result is that a conjecture about strong edge colorings of subcubic graphs proposed by Faudree et al. [Ars Combin. 29 B (1990), 205--211] is false.

preprint2019arXiv

Note on 3-Choosability of Planar Graphs with Maximum Degree 4

Deciding whether a planar graph (even of maximum degree $4$ ) is $3$ -colorable is NP-complete. Determining subclasses of planar graphs being $3$ -colorable has a long history, but since Grötzsch's result that triangle-free planar graphs are such, most of the effort was focused to solving Havel's and Steinberg's conjectures. In this paper, we prove that every planar graph of maximum degree $4$ obtained as a subgraph of the medial graph of any bipartite plane graph is $3$ -choosable. These graphs are allowed to have close triangles (even incident), and have no short cycles forbidden, hence representing an entirely different class than the graphs inferred by the above mentioned conjectures.

preprint2018arXiv

On non-repetitive sequences of arithmetic progressions:the cases $k \in \{4,5,6,7,8\}$

A $d$ -subsequence of a sequence $φ= x_1\dots x_n$ is a subsequence $x_i x_{i+d} x_{i+2d} \dots$ , for any positive integer $d$ and any $i$ , $1 \le i \le n$ . A \textit{ $k$ -Thue sequence} is a sequence in which every $d$ -subsequence, for $1 \le d \le k$ , is non-repetitive, i.e. it contains no consecutive equal subsequences. In 2002, Grytczuk proposed a conjecture that for any $k$ , $k+2$ symbols are enough to construct a $k$ -Thue sequences of arbitrary lengths. So far, the conjecture has been confirmed for $k \in \{1,2,3,5\}$ . Here, we present two different proving techniques, and confirm it for all $k$ , with $2 \le k \le 8$ .

preprint2016arXiv

On incidence coloring conjecture in Cartesian products of graphs

An incidence in a graph $G$ is a pair $(v,e)$ where $v$ is a vertex of $G$ and $e$ is an edge of $G$ incident to $v$ . Two incidences $(v,e)$ and $(u,f)$ are adjacent if at least one of the following holds: $(a)$ $v = u$ , $(b)$ $e = f$ , or $(c)$ $vu \in \{e,f\}$ . An incidence coloring of $G$ is a coloring of its incidences assigning distinct colors to adjacent incidences. It was conjectured that at most $Δ(G) + 2$ colors are needed for an incidence coloring of any graph $G$ . The conjecture is false in general, but the bound holds for many classes of graphs. We introduce some sufficient properties of the two factor graphs of a Cartesian product graph $G$ for which $G$ admits an incidence coloring with at most $Δ(G) + 2$ colors.

preprint2013arXiv

Improved bound on facial parity edge coloring

A facial parity edge coloring of a 2-edge connected plane graph is an edge coloring where no two consecutive edges of a facial walk of any face receive the same color. Additionally, for every face f and every color c either no edge or an odd number of edges incident to f are colored by c. Czap, Jendrol', Kardoš and Sotak showed that every 2-edge connected plane graph admits a facial parity edge coloring with at most 20 colors. We improve this bound to 16 colors.

preprint2013arXiv

l-facial edge colorings of graphs

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 conjectured that 3l + 1 colors suffice for an l-facial edge coloring of any plane graph. We prove that 7 colors suffice for a 2-facial edge coloring of any plane graph and therefore confirm the conjecture for l = 2.

preprint2013arXiv

Star edge coloring of some classes of graphs

\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 subcubic outerplanar graphs, and derive an upper bound for outerplanar graphs.

preprint2013arXiv

Strong edge coloring of planar graphs

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 D has a strong edge coloring with at most 4D + 4 colors. We show that 3D + 6 colors suffice if the graph has girth 6, and 3D colors suffice if the girth is at least 7. Moreover, we show that cubic planar graphs with girth at least 6 can be strongly edge colored with at most 9 colors.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Borut Lužar

Research overview

Is this your work?

11 publications

3-facial edge-coloring of plane graphs

BiqBin: a parallel branch-and-bound solver for binary quadratic problems with linear constraints

Further Extensions of the Grötzsch Theorem

Strong edge colorings of graphs and the covers of Kneser graphs

Note on 3-Choosability of Planar Graphs with Maximum Degree 4

On non-repetitive sequences of arithmetic progressions:the cases $k \in \{4,5,6,7,8\}$

On incidence coloring conjecture in Cartesian products of graphs

Improved bound on facial parity edge coloring

l-facial edge colorings of graphs

Star edge coloring of some classes of graphs

Strong edge coloring of planar graphs

See the researcher in context

Building this map preview

Borut Lužar

Research overview

Is this your work?

11 publications

3-facial edge-coloring of plane graphs

BiqBin: a parallel branch-and-bound solver for binary quadratic problems with linear constraints

Further Extensions of the Grötzsch Theorem

Strong edge colorings of graphs and the covers of Kneser graphs

Note on 3-Choosability of Planar Graphs with Maximum Degree 4

On non-repetitive sequences of arithmetic progressions:the cases k∈{4,5,6,7,8}k \in \{4,5,6,7,8\}k∈{4,5,6,7,8}

On incidence coloring conjecture in Cartesian products of graphs

Improved bound on facial parity edge coloring

l-facial edge colorings of graphs

Star edge coloring of some classes of graphs

Strong edge coloring of planar graphs

See the researcher in context

Building this map preview

On non-repetitive sequences of arithmetic progressions:the cases $k \in \{4,5,6,7,8\}$