PDF

Discussiones Mathematicae Graph Theory  17(2) (1997) 311-313
DOI: https://doi.org/10.7151/dmgt.1058

PARTITION PROBLEMS AND KERNELS OF GRAPHS

Izak Broere Department of Mathematics, Rand Afrikaans University P.O. Box 524, Auckland Park, 2006 South Africa email: ib@rau3.rau.ac.za

Péter Hajnal Bolyai Intézet, University of Szeged Aradi Vértanúk tere 1., Szeged, Hungary 6720 email: hajnal@inf.u-szeged.hu

Peter Mihók Mathematical Institute, Slovak Academy of Sciences Greákova 6, 040 01 Koice email: mihok@Košice.upjs.sk

1. Introduction

The graphs we consider are finite, simple and undirected. The number of vertices in a longest path in a graph G is denoted by τ(G). For positive integers k₁ and k₂ a graph G is (τ,k₁,k₂)-partitionable if there exists a partition { V₁,V₂ } of V(G) such that τ(G[ V₁] ) ≤ k₁ and τ(G[ V₂] ) ≤ k₂. If this can be done for every pair of positive integers (k₁,k₂) satisfying k₁ + k₂ = τ(G), we say that G is τ- partitionable.

Let H_v denote the fact that the graph H is rooted at v. The set S ⊆ V(G) is an H_v-kernel if

(i)	there is no subgraph of G[S] isomorphic to H and
(ii)	for every x ∈ V(G) - S there is a subgraph of G[S ∪{x }] isomorphic to Hv with its root v at x.

Similarly, a graph is H_v-saturated if it has a subset S ⊆ V(G) such that

(i)	H is not a subgraph of G[S] and
(ii)	for every x ∈ V(G) - S which is adjacent to some vertex of S the graph H is a subgraph of G[S ∪{x}] with its root v at x.

A graph G is called decomposable if it is the join of two graphs.

2. The problems

We start with a problem which is formulated as a conjecture in [3] and [1] (see also in [2]).

Conjecture 1. Every graph is τ-partitionable.

In [1] it is shown amongst others that every decomposable graph is τ-partitionable.

For a given (rooted) graph H_v, the question whether every graph G has an H_v-kernel is discussed in [2], [4] and [5]. It is shown amongst others that

(a)	Every graph has an Hv-kernel if and only if every graph is Hv-saturated.
(b)	Every graph has a Pv-kernel where Pv is a path of order at most six and v is an endvertex of P.
(c)	Every graph has an Sv-kernel where Sv is a star and v is the center of the star or v is an endvertex of the star.

Clearly, if H_v is a vertex transitive graph, then every graph has an H_v-kernel (any maximal set of vertices inducing an H_v-free graph is an H_v-kernel). The fact that there are graphs H_v and G for which G has no H_v-kernel is illustrated in [2] and [4]. The general problem therefore is

Problem. Describe the rooted graphs H_v for which every graph G has an H_v-kernel.

Let the path P_v of order n be rooted at an endvertex. If every graph G has a P_v-kernel for every n then Conjecture 1 is true: If τ(G) = k₁ + k₂, let V₁ be a Q_v-kernel where Q_v is a path (rooted at an endvertex) of order k₁ + 1 and let V₂ = V(G) - S. From (b) we immediately obtain that every graph is (τ,k₁,k₂)-partitionable if min{k₁,k₂} ≤ 5.

We are inclined to think that the following conjecture is also true for every path P_v rooted at an endvertex v.

Conjecture 2. Every graph has a P_v-kernel.

References

[1]	I. Broere, M. Dorfling J. Dunbar and M. Frick, A path(ological) partition problem (submitted).
[2]	P. Hajnal, Graph partitions (in Hungarian) (Thesis, supervised by L. Lovász, J.A. University, Szeged, 1984).
[3]	J.M. Laborde, C. Payan and N.H. Xuong, Independent sets and longest directed paths in digraphs, in: Graphs and other combinatorial topics (Prague, 1982), (Teubner-Texte Math., 59, 1983), 173-177.
[4]	P. Mihók, Problem 4, p. 86, in: Graphs, Hypergraphs and Matroids (M. Borowiecki and Z. Skupień, eds., Zielona Góra 1985).
[5]	J. Vronka, Vertex sets of graphs with prescribed properties (in Slovak) (Thesis, supervised by P. Mihók, P.J. Šafárik University, Košice, 1986).