Source author record

Roman Sotak

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

2works

1topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

On the cyclic coloring conjecture

A cyclic coloring of a plane graph $G$ 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 coloring of a plane graph $G$ is its cyclic chromatic number $χ_c(G)$ . Let $Δ^*(G)$ be the maximum face degree of a graph $G$ . In this note we show that to prove the Cyclic Coloring Conjecture of Borodin from 1984, saying that every connected plane graph $G$ has $χ_c(G) \leq \lfloor \frac{3}{2}Δ^*(G)\rfloor$ , it is enough to do it for subdivisions of simple $3$ -connected plane graphs. We have discovered four new different upper bounds on $χ_c(G)$ for graphs $G$ from this restricted family; three bounds of them are tight. As corollaries, we have shown that the conjecture holds for subdivisions of plane triangulations, simple $3$ -connected plane quadrangulations, and simple $3$ -connected plane pentagulations with an even maximum face degree, for regular subdivisions of simple $3$ -connected plane graphs of maximum degree at least 10, and for subdivisions of simple $3$ -connected plane graphs having the maximum face degree large enough in comparison with the number of vertices of their longest paths consisting only of vertices of degree two.

preprint2012arXiv

Rainbow numbers for graphs with cyclomatic number at most two

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 subgraph H in Kn has at least two edges of the same colour. Equivalently, any edge-colouring of Kn with at least rb(n;H) = f(n;H)+1 colours contains a rainbow copy of H: The numbers f(n;H) and rb(Kn;H) are called anti-ramsey numbers and rainbow numbers, respectively. In this paper we will classify the rainbow number for a given graph H with respect to its cyclomatic number. Let H be a graph of order p >= 4 and cyclomatic number v(H) >= 2: Then rb(Kn;H) cannot be bounded from above by a function which is linear in n: If H has cyclomatic number v(H) = 1; then rb(Kn;H) is linear in n: We will compute all rainbow numbers for the bull B; which is the unique graph with 5 vertices and degree sequence (1; 1; 2; 3; 3): Furthermore, we will compute some rainbow numbers for the diamond D = K_4 - e; for K_2;3; and for the house H (complement of P_5).

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.