# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

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

# Discussiones Mathematicae Graph Theory

## 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

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