Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

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

On graphs G for which both g and G̅ are claw-free

100%

Fujita S.

Discussiones Mathematicae Graph Theory

2005

tom 25

nr 3

267-272

Let G be a graph with |V(G)| ≥ 10. We prove that if both G and G̅ are claw-free, then min{Δ(G), Δ(G̅)} ≤ 2. As a generalization of this result in the case where |V(G)| is sufficiently large, we also prove that if both G and G̅ are $K_{1,t}$-free, then min{Δ(G),Δ(G̅)} ≤ r(t- 1,t)-1 where r(t-1,t) is the Ramsey number.

The Balanced Decomposition Number of TK4 and Series-Parallel Graphs

63%

Fujita S., Liu H.

Discussiones Mathematicae Graph Theory

2013

tom 33

nr 2

347-359

A balanced colouring of a graph G is a colouring of some of the vertices of G with two colours, say red and blue, such that there is the same number of vertices in each colour. The balanced decomposition number f(G) of G is the minimum integer s with the following property: For any balanced colouring of G, there is a partition V (G) = V1 ∪˙ · · · ∪˙ Vr such that, for every i, Vi induces a connected subgraph of order at most s, and contains the same number of red and blue vertices. The function f(G) was introduced by Fujita and Nakamigawa in 2008. They conjectured that f(G) ≤ ⌊n 2 ⌋ + 1 if G is a 2-connected graph on n vertices. In this paper, we shall prove two partial results, in the cases when G is a subdivided K4, and a 2-connected series-parallel graph.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Fujita S.

1 Liu H.

1 2013

1 2005

Wyniki wyszukiwania

On graphs G for which both g and G̅ are claw-free

The Balanced Decomposition Number of TK4 and Series-Parallel Graphs