# 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  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 ,  and . 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  and . 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

  I. Broere, M. Dorfling J. Dunbar and M. Frick, A path(ological) partition problem (submitted).  P. Hajnal, Graph partitions (in Hungarian) (Thesis, supervised by L. Lovász, J.A. University, Szeged, 1984).  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.  P. Mihók, Problem 4, p. 86, in: Graphs, Hypergraphs and Matroids (M. Borowiecki and Z. Skupień, eds., Zielona Góra 1985).  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).