Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: WORM coloring

Sortuj według:

Ogranicz wyniki do:

K3-Worm Colorings of Graphs: Lower Chromatic Number and Gaps in the Chromatic Spectrum

100%

Bujtás C., Tuza Z.

Discussiones Mathematicae Graph Theory

2016

tom 36

nr 3

759-772

A K3-WORM coloring of a graph G is an assignment of colors to the vertices in such a way that the vertices of each K3-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 K3-WORM colorable graphs which have a K3-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.

WORM Colorings of Planar Graphs

88%

Czap J., Jendrol’ S., Valiska J.

Discussiones Mathematicae Graph Theory

2017

tom 37

nr 2

353-368

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) ≤ 2 if |V (F)| ≥ 3 and H contains a cycle, (b) W−F,H(G) ≤ 3 if |V (F)| ≥ 4 and H is a forest with Δ (H) ≥ 3, (c) W−F,H(G) ≤ 4 if |V (F)| ≥ 5 and H is a forest with 1 ≤ Δ (H) ≤ 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.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

1 Bujtás C.

1 Czap J.

1 Jendrol’ S.

1 Tuza Z.

1 Valiska J.

1 2017

1 2016

Wyniki wyszukiwania

K3-Worm Colorings of Graphs: Lower Chromatic Number and Gaps in the Chromatic Spectrum

WORM Colorings of Planar Graphs