ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

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

Discussiones Mathematicae Graph Theory


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


Izak Broere

Department of Mathematics, Rand Afrikaans University
P.O. Box 524, Auckland Park, 2006 South Africa


Péter Hajnal

Bolyai Intézet, University of Szeged
Aradi Vértanúk tere 1., Szeged, Hungary 6720


Peter Mihók

Mathematical Institute, Slovak Academy of Sciences
Greákova 6, 040 01 Koice

email: mihok@Koš

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.


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