MU SAV

Bratislava, Slovakia
Bratislava, Slovakia
SEARCH FILTERS
Time filter
Source Type

Kochol M.,MU SAV | Skrekovski R.,University of Ljubljana
Information Processing Letters | Year: 2012

The well-known Brooks Theorem says that each graph G of maximum degree k≥3 is k-colorable unless G=Kk+1. We generalize this theorem by allowing higher degree vertices with prescribed types of neighborhood. © 2011 Elsevier B.V. All rights reserved.


Kochol M.,MU SAV | Skrekovski R.,University of Ljubljana
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2011

We study a (k + 1)-coloring problem in a class of (k,s)-dart graphs, k,s ≥ 2, where each vertex of degree at least k + 2 belongs to a (k,i)-diamond, i ≤ s. We prove that dichotomy holds, that means the problem is either NP-complete (if k < s), or can be solved in linear time (if k ≥ s). In particular, in the latter case we generalize the classical Brooks Theorem, that means we prove that a (k, s)-dart graph, k ≥ max {2,s}, is (k + 1)-colorable unless it contains a component isomorphic to Kk + 2. © 2011 Springer-Verlag.


Kochol M.,MU SAV
Journal of Combinatorial Theory. Series B | Year: 2017

Tutte–Grothendieck invariants of graphs are mappings from a class of graphs to a commutative ring that are characterized recursively by contraction-deletion rules. Well known examples are the Tutte, chromatic, tension and flow polynomials. Suppose that an edge cut C divides a graph G into two parts G1, G1 ′ and that G1, G1 ′ are the sets of minors of G whose edge sets consist of C and edges of G1, G1 ′, respectively. We study determinant formulas evaluating a Tutte–Grothendieck invariant of G from the Tutte–Grothendieck invariants of graphs from G1 and G1 ′. © 2017 Elsevier Inc.


Kochol M.,MU SAV | Krivonakova N.,FPV ZU | Smejova S.,FPV ZU | Srankova K.,FPV ZU
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2011

Recently we have developed a method excluding certain subgraphs from a smallest counterexample to the 5-flow conjecture. This is based on comparing ranks of two matrices of large size. The aim of this paper is to be more effective by applying these methods so that we reduce the size of matrices used in the computation. © 2011 Springer-Verlag.


Kochol M.,MU SAV
Journal of Combinatorial Optimization | Year: 2016

We introduce canonical forms that represent certain equivalence classes of totally cyclic and acyclic orientations of graphs and present a polynomial algorithms for their constructions. The forms are used in new formulas evaluating tension and flow polynomials on graphs. © 2014, Springer Science+Business Media New York.


Kochol M.,MU SAV
Information Processing Letters | Year: 2012

We show that for each even m>2 and n≥4m-2, there exists a latin (n×n×(n-m))-parallelepiped that cannot be extended to a latin (n×n×(n-m+1))-parallelepiped. © 2012 Elsevier B.V. All rights reserved.


Kochol M.,MU SAV | Krivonakova N.,FPVzu | Smejova S.,FPVzu | Srankova K.,FPVzu
Information Processing Letters | Year: 2011

The 5-flow conjecture of Tutte is that every bridgeless graph has a nowhere-zero 5-flow. Recently Kochol developed a method giving lower bounds for the girth of a smallest counterexample to the 5-flow conjecture. It consists in comparing rank of a matrix with rank of its submatrix. In this paper we present a reduction of the size of these matrices. © 2010 Elsevier B.V. All rights reserved.


Kochol M.,MU SAV
Journal of Combinatorial Theory. Series B | Year: 2010

The famous 5-flow conjecture of Tutte is that every bridgeless graph has a nowhere-zero 5-flow. We show that a smallest counterexample to this conjecture must have girth at least eleven. © 2009 Elsevier Inc.


Kochol M.,MU SAV
Journal of Combinatorial Optimization | Year: 2014

In 1913, Birkhoff proved that the smallest counterexample to the Four Color Theorem must be an internally 6-connected planar graph. We use methods of linear algebra for an alternative proof of this statement. © 2012 Springer Science+Business Media New York.

Loading MU SAV collaborators
Loading MU SAV collaborators