DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory  17(2) (1997) 311-313
DOI: 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 k1 and k2 a graph G is (τ,k1,k2)-partitionable if there exists a partition { V1,V2 } of V(G) such that τ(G[ V1] ) ≤ k1 and τ(G[ V2] ) ≤ k2. If this can be done for every pair of positive integers (k1,k2) satisfying k1 + k2 = τ(G), we say that G is τ- partitionable.


Let Hv denote the fact that the graph H is rooted at v. The set S ⊆ V(G) is an Hv-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 Hv-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 Hv, the question whether every graph G has an Hv-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 Hv is a vertex transitive graph, then every graph has an Hv-kernel (any maximal set of vertices inducing an Hv-free graph is an Hv-kernel). The fact that there are graphs Hv and G for which G has no Hv-kernel is illustrated in [2] and [4]. The general problem therefore is

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

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

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

Conjecture 2. Every graph has a Pv-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).