5 papers
On the cyclic coloring conjecture
Stanislav Jendrol, Roman Sotak
A cyclic coloring of a plane graph is a coloring of its vertices such that vertices incident with the same face have distinct colors. The minimum number of colors in a cyclic c…
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…
Rainbow numbers for graphs with cyclomatic number at most two
Ingo Schiermeyer, Roman Sotak
For a given graph H and n ? 1; let f(n;H) denote the maximum number m for which it is possible to colour the edges of the complete graph Kn with m colours in such a way that each s…