Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

On Longest Cycles in Essentially 4-Connected Planar Graphs

100%

Fabrici I., Harant J., Jendroľ S.

Discussiones Mathematicae Graph Theory

2016

tom 36

nr 3

565-575

A planar 3-connected graph G is essentially 4-connected if, for any 3-separator S of G, one component of the graph obtained from G by removing S is a single vertex. Jackson and Wormald proved that an essentially 4-connected planar graph on n vertices contains a cycle C such that [...] . For a cubic essentially 4-connected planar graph G, Grünbaum with Malkevitch, and Zhang showed that G has a cycle on at least ¾ n vertices. In the present paper the result of Jackson and Wormald is improved. Moreover, new lower bounds on the length of a longest cycle of G are presented if G is an essentially 4-connected planar graph of maximum degree 4 or G is an essentially 4-connected maximal planar graph.

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

On the strong parity chromatic number

100%

Czap J., Jendroľ S., Kardoš F.

Discussiones Mathematicae Graph Theory

2011

tom 31

nr 3

587-600

A vertex colouring of a 2-connected plane graph G is a strong parity vertex colouring if for every face f and each colour c, the number of vertices incident with f coloured by c is either zero or odd. Czap et al. in [9] proved that every 2-connected plane graph has a proper strong parity vertex colouring with at most 118 colours. In this paper we improve this upper bound for some classes of plane graphs.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Jendroľ S.

1 Czap J.

1 Fabrici I.

1 Harant J.

1 Kardoš F.

1 2016

1 2011

Wyniki wyszukiwania

On Longest Cycles in Essentially 4-Connected Planar Graphs

On the strong parity chromatic number