Zobrazeno 1 - 10
of 161
pro vyhledávání: '"Soták, Roman"'
A strong edge-coloring of a graph is a proper edge-coloring, in which the edges of every path of length 3 receive distinct colors; in other words, every pair of edges at distance at most 2 must be colored differently. The least number of colors neede
Externí odkaz:
http://arxiv.org/abs/2410.01049
We show that every cubic graph on $n$ vertices contains a spanning subgraph in which the number of vertices of each degree deviates from $\frac{n}{4}$ by at most $\frac{1}{2}$, up to three exceptions. This resolves the conjecture of Alon and Wei (Irr
Externí odkaz:
http://arxiv.org/abs/2408.16121
A graph/multigraph $G$ is locally irregular if endvertices of every its edge possess different degrees. The locally irregular edge coloring of $G$ is its edge coloring with the property that every color induces a locally irregular sub(multi)graph of
Externí odkaz:
http://arxiv.org/abs/2405.13893
Autor:
Oravcová, Janka, Soták, Roman
For $D$ being a subset of positive integers, the integer distance graph is the graph $G(D)$, whose vertex set is the set of integers, and edge set is the set of all pairs $uv$ with $|u-v| \in D$. It is known that $\chi(G(D)) \leq |D|+1$. This article
Externí odkaz:
http://arxiv.org/abs/2401.12347
We consider the robust chromatic number $\chi_1(G)$ of planar graphs $G$ and show that there exists an infinite family of planar graphs $G$ with $\chi_1(G) = 3$, thus solving a recent problem of Bacs\'{o}~et~al. (The robust chromatic number of graphs
Externí odkaz:
http://arxiv.org/abs/2401.08324
Autor:
Lužar, Borut, Maceková, Mária, Rindošová, Simona, Soták, Roman, Sroková, Katarína, Štorgel, Kenny
A graph is {\em locally irregular} if no two adjacent vertices have the same degree. A {\em locally irregular edge-coloring} of a graph $G$ is such an (improper) edge-coloring that the edges of any fixed color induce a locally irregular graph. Among
Externí odkaz:
http://arxiv.org/abs/2210.04649
A matching $M$ in a graph $G$ is {\em semistrong} if every edge of $M$ has an endvertex of degree one in the subgraph induced by the vertices of $M$. A {\em semistrong edge-coloring} of a graph $G$ is a proper edge-coloring in which every color class
Externí odkaz:
http://arxiv.org/abs/2208.13297
A {\em conflict-free coloring} of a graph {\em with respect to open} (resp., {\em closed}) {\em neighborhood} is a coloring of vertices such that for every vertex there is a color appearing exactly once in its open (resp., closed) neighborhood. Simil
Externí odkaz:
http://arxiv.org/abs/2202.02570
Publikováno v:
In Applied Mathematics and Computation 1 June 2024 470
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
Externí odkaz:
http://arxiv.org/abs/2101.04768