Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 3

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Some totally 4-choosable multigraphs

100%
Woodall D.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 3
425-455
EN
It is proved that if G is multigraph with maximum degree 3, and every submultigraph of G has average degree at most 2(1/2) and is different from one forbidden configuration C⁺₄ with average degree exactly 2(1/2), then G is totally 4-choosable; that is, if every element (vertex or edge) of G is assigned a list of 4 colours, then every element can be coloured with a colour from its own list in such a way that no two adjacent or incident elements are coloured with the same colour. This shows that the List-Total-Colouring Conjecture, that ch''(G) = χ''(G) for every multigraph G, is true for all multigraphs of this type. As a consequence, if G is a graph with maximum degree 3 and girth at least 10 that can be embedded in the plane, projective plane, torus or Klein bottle, then ch''(G) = χ''(G) = 4. Some further total choosability results are discussed for planar graphs with sufficiently large maximum degree and girth.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Defective choosability of graphs in surfaces

100%
Woodall D.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 3
441-459
EN
It is known that if G is a graph that can be drawn without edges crossing in a surface with Euler characteristic ε, and k and d are positive integers such that k ≥ 3 and d is sufficiently large in terms of k and ε, then G is (k,d)*-colorable; that is, the vertices of G can be colored with k colors so that each vertex has at most d neighbors with the same color as itself. In this paper, the known lower bound on d that suffices for this is reduced, and an analogous result is proved for list colorings (choosability). Also, the recent result of Cushing and Kierstead, that every planar graph is (4,1)*-choosable, is extended to $K_{3,3}$-minor-free and K₅-minor-free graphs.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Short cycles of low weight in normal plane maps with minimum degree 5

63%
Borodin O., Woodall D.
Discussiones Mathematicae Graph Theory
|
1998
|
tom 18
|
nr 2
159-164
EN
In this note, precise upper bounds are determined for the minimum degree-sum of the vertices of a 4-cycle and a 5-cycle in a plane triangulation with minimum degree 5: w(C₄) ≤ 25 and w(C₅) ≤ 30. These hold because a normal plane map with minimum degree 5 must contain a 4-star with $w(K_{1,4}) ≤ 30$. These results answer a question posed by Kotzig in 1979 and recent questions of Jendrol' and Madaras.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.