Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: colouring

Sortuj według:

Ogranicz wyniki do:

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

Colouring graphs with prescribed induced cycle lengths

100%

Randerath B., Schiermeyer I.

Discussiones Mathematicae Graph Theory

2001

tom 21

nr 2

267-281

In this paper we study the chromatic number of graphs with two prescribed induced cycle lengths. It is due to Sumner that triangle-free and P₅-free or triangle-free, P₆-free and C₆-free graphs are 3-colourable. A canonical extension of these graph classes is $𝓖^I(4,5)$, the class of all graphs whose induced cycle lengths are 4 or 5. Our main result states that all graphs of $𝓖^I(4,5)$ are 3-colourable. Moreover, we present polynomial time algorithms to 3-colour all triangle-free graphs G of this kind, i.e., we have polynomial time algorithms to 3-colour every $G ∈ 𝓖^I(n₁,n₂)$ with n₁,n₂ ≥ 4 (see Table 1). Furthermore, we consider the related problem of finding a χ-binding function for the class $𝓖^I(n₁,n₂)$. Here we obtain the surprising result that there exists no linear χ-binding function for $𝓖^I(3,4)$.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Randerath B.

1 Schiermeyer I.

1 2001

Wyniki wyszukiwania

Colouring graphs with prescribed induced cycle lengths