Juraj Stacho

most cited4-coloring

P_{6}

-free graphs with no induced 5-cycles

7 citations · 7 across the 3 of their papers we have counts for

collaborators

3 papers

cs.DM2014

Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm

Mathew Francis, Pavol Hell, Juraj Stacho

A circular-arc graph is the intersection graph of arcs of a circle. It is a well-studied graph model with numerous natural applications. A certifying algorithm is an algorithm that…

cs.DM2014★ 7 cited

4-coloring $P_{6}$ -free graphs with no induced 5-cycles

Maria Chudnovsky, Peter Maceli, Juraj Stacho +1

We show that the 4-coloring problem can be solved in polynomial time for graphs with no induced 5-cycle $C_{5}$ and no induced 6-vertex path $P_{6}$ .

cs.CC2010

Dichotomy for tree-structured trigraph list homomorphism problems

Tomás Feder, Pavol Hell, David G. Schell +1

Trigraph list homomorphism problems (also known as list matrix partition problems) have generated recent interest, partly because there are concrete problems that are not known to…

Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm

4-coloring P6​-free graphs with no induced 5-cycles

Dichotomy for tree-structured trigraph list homomorphism problems

4-coloring $P_{6}$ -free graphs with no induced 5-cycles