Wyniki wyszukiwania

1

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

EN

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)$.

2

On well-covered graphs of odd girth 7 or greater

100%

Randerath B., Vestergaard P.

Discussiones Mathematicae Graph Theory

|

2002

|

tom 22

|

nr 1

159-172

EN

A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer [14] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. One of the most challenging problems in this area, posed in the survey of Plummer [15], is to find a good characterization of well-covered graphs of girth 4. We examine several subclasses of well-covered graphs of girth ≥ 4 with respect to the odd girth of the graph. We prove that every isolate-vertex-free well-covered graph G containing neither C₃, C₅ nor C₇ as a subgraph is even very well-covered. Here, a isolate-vertex-free well-covered graph G is called very well-covered, if G satisfies α(G) = n/2. A vertex set D of G is dominating if every vertex not in D is adjacent to some vertex in D. The domination number γ(G) is the minimum order of a dominating set of G. Obviously, the inequality γ(G) ≤ α(G) holds. The family $𝓖_{γ=α}$ of graphs G with γ(G) = α(G) forms a subclass of well-covered graphs. We prove that every connected member G of $𝓖_{γ=α}$ containing neither C₃ nor C₅ as a subgraph is a K₁, C₄,C₇ or a corona graph.

3

Bounds on the global offensive k-alliance number in graphs

81%

Chellali M., Haynes T., Randerath B., Volkmann L.

Discussiones Mathematicae Graph Theory

|

2009

|

tom 29

|

nr 3

597-613

EN

Let G = (V(G),E(G)) be a graph, and let k ≥ 1 be an integer. A set S ⊆ V(G) is called a global offensive k-alliance if |N(v)∩S| ≥ |N(v)-S|+k for every v ∈ V(G)-S, where N(v) is the neighborhood of v. The global offensive k-alliance number $γₒ^k(G)$ is the minimum cardinality of a global offensive k-alliance in G. We present different bounds on $γₒ^k(G)$ in terms of order, maximum degree, independence number, chromatic number and minimum degree.

Ograniczanie wyników

3 Discussiones Mathematicae Graph Theory

3 Randerath B.

1 Chellali M.

1 Haynes T.

1 Schiermeyer I.

1 Vestergaard P.

1 Volkmann L.

1 2009

1 2002

1 2001

Colouring graphs with prescribed induced cycle lengths

On well-covered graphs of odd girth 7 or greater

Bounds on the global offensive k-alliance number in graphs