Temat: WORM-coloring - Prolib Integro

Skocz do pozycji: 1.

Tytuł:: Singular Turán Numbers and Worm-Colorings
Autorzy:: Gerbner, Dániel
Patkós, Balázs
Vizer, Máté
Tuza, Zsolt
Tematy:: Turán number
WORM-coloring
singular Turán numbers; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/32222590.pdf Link otwiera się w nowym oknie
Opis:: A subgraph G of H is singular if the vertices of G either have the same degree in H or have pairwise distinct degrees in H. The largest number of edges of a graph on n vertices that does not contain a singular copy of G is denoted by T_S(n, G). Caro and Tuza in [Singular Ramsey and Turán numbers, Theory Appl. Graphs 6 (2019) 1–32] obtained the asymptotics of T_S(n, G) for every graph G, but determined the exact value of this function only in the case G = K₃ and n ≡ 2 (mod 4). We determine T_S(n, K3) for all n ≡ 0 (mod 4) and n ≡ 1 (mod 4), and also T_S(n, K_r+1) for large enough n that is divisible by r. We also explore the connection to the so-called G-WORM colorings (vertex colorings without rainbow or monochromatic copies of G) and obtain new results regarding the largest number of edges that a graph with a G-WORM coloring can have.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 2.

Tytuł:: WORM Colorings of Planar Graphs
Autorzy:: Czap, J.
Jendrol’, S.
Valiska, J.
Tematy:: plane graph
monochromatic path
rainbow path
WORM coloring
facial coloring; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31341972.pdf Link otwiera się w nowym oknie
Opis:: Given three planar graphs $F$, $H$, and $G$, an $(F,H)$-WORM coloring of $G$ is a vertex coloring such that no subgraph isomorphic to $F$ is rainbow and no subgraph isomorphic to $H$ is monochromatic. If $G$ has at least one $(F,H)$-WORM coloring, then $ W_{F,H}^- (G)$ denotes the minimum number of colors in an $(F,H)$-WORM coloring of $G$. We show that (a) $W_{F,H}^- (G) \le 2 $ if $ |V (F)| \ge 3$ and $H$ contains a cycle, (b) $W_{F,H}^- (G) \le 3 $ if $ |V (F)| \ge 4$ and $H$ is a forest with $ \Delta (H) \ge 3$, (c) $W_{F,H}^- (G) \le 4 $ if $ |V (F)| \ge 5$ and $H$ is a forest with $1 \le \Delta (H) \le 2 $. The cases when both $F$ and $H$ are nontrivial paths are more complicated; therefore we consider a relaxation of the original problem. Among others, we prove that any 3-connected plane graph (respectively outerplane graph) admits a 2-coloring such that no facial path on five (respectively four) vertices is monochromatic.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 3.

Tytuł:: Improved bounds for some facially constrained colorings
Autorzy:: Štorgel, Kenny
Tematy:: plane graph
facial coloring
facial-parity edge-coloring
facial-parity vertex-coloring
WORM coloring; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/59586505.pdf Link otwiera się w nowym oknie
Opis:: A facial-parity edge-coloring of a $2$-edge-connected plane graph is a facially-proper edge-coloring in which every face is incident with zero or an odd number of edges of each color. A facial-parity vertex-coloring of a $2$-connected plane graph is a proper vertex-coloring in which every face is incident with zero or an odd number of vertices of each color. Czap and Jendroľ in [Facially-constrained colorings of plane graphs: A survey, Discrete Math. 340 (2017) 2691–2703], conjectured that $10$ colors suffice in both colorings. We present an infinite family of counterexamples to both conjectures. A facial $(P_{k}, P_{ \mathcal{l} } )$-WORM coloring of a plane graph $G$ is a vertex-coloring such that $G$ contains neither rainbow facial $k$-path nor monochromatic facial $\mathcal{l} $-path. Czap, Jendroľ and Valiska in [WORM colorings of planar graphs, Discuss. Math. Graph Theory 37 (2017) 353–368], proved that for any integer $n\ge 12$ there exists a connected plane graph on $n$ vertices, with maximum degree at least $6$, having no facial $(P_{3},P_{3})$-WORM coloring. They also asked whether there exists a graph with maximum degree $4$ having the same property. We prove that for any integer $n\ge 18$, there exists a connected plane graph, with maximum degree $4$, with no facial $(P_{3},P_{3})$-WORM coloring.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 4.

Tytuł:: K₃-WORM Colorings of Graphs: Lower Chromatic Number and Gaps in the Chromatic Spectrum
Autorzy:: Bujtás, Csilla
Tuza, Zsolt
Tematy:: WORM coloring
lower chromatic number
feasible set
gap in the chromatic spectrum; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31340789.pdf Link otwiera się w nowym oknie
Opis:: A K₃-WORM coloring of a graph G is an assignment of colors to the vertices in such a way that the vertices of each K₃-subgraph of G get precisely two colors. We study graphs G which admit at least one such coloring. We disprove a conjecture of Goddard et al. [Congr. Numer. 219 (2014) 161-173] by proving that for every integer k ≥ 3 there exists a K3-WORM-colorable graph in which the minimum number of colors is exactly k. There also exist K₃-WORM colorable graphs which have a K₃-WORM coloring with two colors and also with k colors but no coloring with any of 3, . . ., k − 1 colors. We also prove that it is NP-hard to determine the minimum number of colors, and NP-complete to decide k-colorability for every k ≥ 2 (and remains intractable even for graphs of maximum degree 9 if k = 3). On the other hand, we prove positive results for d-degenerate graphs with small d, also including planar graphs.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Informacja

Wyszukujesz frazę "WORM-coloring" wg kryterium: Temat