Paul Manuel
email: pauldmanuel@gmail.com

Revisiting path-type covering and partitioning problems

Keywords: Survey, covering and partitioning problems, paths, induced paths and isometric paths AMS Subj. Class.: 05C12, 05C70, 05C76; 68Q17

published or not. The documents may come

Revisiting path-type covering and partitioning problems

This is a survey article which is at the initial stage. The author will appreciate to receive your comments and contributions to improve the quality of the article. The author's contact address is pauldmanuel@gmail.com.

Introduction

An undirected connected graph is represented by G(V, E) where V is the vertex set and E is the edge set. There are several types of covering problems such as covering the vertex set by stars (domination problem), covering the vertex set by cliques (the clique covering problem), covering the vertex set by independent sets (the coloring problem), and covering the vertex set by path-types. A path-type means a path, an induced path or an isometric path. A path P is an induced path in G if the subgraph induced by the vertices of P is a path. An induced path is also called a chordless path [START_REF] Mezzini | On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs[END_REF]. Let us recall that isometric path and geodesic are other names for shortest path.

Mathematicians agree that the term "covering" is over-used or inappropriatelyused in graph theory. In set theory, there are two different terminologies: set covering problem and set hitting problem. The edge cover problem is a special case of set covering problem while the vertex cover problem is a special case of set hitting problem. While set theorists distinguished the two concepts by "covering" and "hitting", graph theorists chose to use the same term "covering" to mean two different concepts. Thus, right in the beginning, the term "cover" was over-used. The trend has been continuing. It is not uncommon that researchers use the term "path cover problem" to mean "path partition problem" and use the same term to mean "induced path cover problem". It is observed that the concepts "cover" & "partition" and the terms "path" & "induced path" are used inappropriately. There is no consistency in the usage of notations too. For example, while some authors use the notation π to represent the path cover number, others use the notation µ to represent the same concept of path cover number. These "inconsistent notation" and "inappropriate terminologies" lead novice readers to confusion. This situation demands an article that classifies and simplifies the notations and terminologies of path-type covering and partitioning problems.

In this article, we divide the "theory of decomposition" into six problems and classify the literatures accordingly. We also bring their related concepts together under one umbrella. This article targets young researchers in graph theory. The benefit of this article is that it exposes the gap and open space in research area under each problem. The article highlights that there is plenty of research to be done in this topic. In addition, this article will save time for young researchers to choose a right research topic in this domain and it may be a reference to apply common notations and appropriate terminologies in their research articles.

In section 3, some relevant problems such as the k-path cover problem, the S-path cover problem and k-path vertex cover problem are discussed. Since these topics are not our main focus, we do not provide elaborate literature survey for these problems.

In section 4, the significance of Gallai-Milgram theorem and Berge path partition conjecture is highlighted. The three cover problems are discussed in section 5 and the three partition problems are studied in section 6.

Path-type covering and partitioning problems

Brause and Krivoš-Belluš [START_REF] Brause | On a relation between k-path partition and k-path vertex cover[END_REF] state that the cover problem and the partition problem are central problems in graph theory. One such well-known concept in graph theory is "clique covering" and "clique partitioning" [START_REF] Erdős | Clique partitions and clique coverings[END_REF]. A path cover of G is a set of paths such that every vertex v ∈ V belongs to at least one path, whereas a path partition of G is a set of paths such that every vertex v ∈ V belongs to exactly one path [START_REF]Berge's conjecture on directed path partitions -a survey[END_REF]. In a path partition, the paths are mutually vertex-disjoint. A few authors use the term "vertex-disjoint path cover" to mean "path partition" [START_REF] Barioli | Computation of minimal rank and path cover number for certain graphs[END_REF]. The following six invariants (See Figure 1) are defined here:

(1) The path cover number of G, denoted by π c (G), is the cardinality of a minimum path cover of G. The path cover problem is to find a path cover of minimum cardinality in G.

(2) The induced path cover number of G, denoted by ρ c (G), is the cardinality of a minimum induced path cover of G. The induced path cover problem is to find an induced path cover of minimum cardinality in G.

(3) The isometric path cover number of G, denoted by ip c (G), is the cardinality of a minimum isometric path cover of G. The isometric path cover problem is to find an isometric path cover of minimum cardinality in G.

(4) The path partition number of G, denoted by π p (G), is the cardinality of a minimum path partition of G. The path partition problem is to find a path partition of minimum cardinality in G.

(5) The induced path partition number of G, denoted by ρ p (G), is the cardinality of a minimum induced path partition of G. The induced path partition problem is to find an induced path partition of minimum cardinality in G.

(6) The isometric path partition number of G, denoted by ip p (G), is the cardinality of a minimum isometric path partition of G. The isometric path partition problem is to find an isometric path partition of minimum cardinality in G. While some authors [START_REF] Rao | Linear algorithm for optimal path problem on interval graphs[END_REF][START_REF] Chartrand | The induced path number of bipartite graphs[END_REF][START_REF] Erdős | Clique partitions and clique coverings[END_REF][START_REF] Hartman | Variations on the Gallai-Milgram theorem[END_REF][START_REF]Berge's conjecture on directed path partitions -a survey[END_REF][START_REF]Induced-path partition on graphs with special blocks[END_REF][START_REF] Skupién | Path partitions for vertices and Hamiltonicity of graphs[END_REF][START_REF] Srikant | Optimal path cover problem on block graphs and bipartite permutation graphs[END_REF][START_REF] Pak | Optimal path cover problem on block graphs[END_REF][START_REF] Yan | The path-partition problem in block graphs[END_REF] use the term "path partition", others [START_REF] Asdre | An optimal parallel solution for the path cover problem on P 4 -sparse graphs[END_REF][START_REF] Barioli | Computation of minimal rank and path cover number for certain graphs[END_REF][START_REF] Catral | Zero forcing number, maximum nullity, and path cover number of subdivided graphs[END_REF][START_REF] Corneil | LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs[END_REF][START_REF] Hung | Solving the path cover problem on circulararc graphs by using an approximation algorithm[END_REF][START_REF] Magnant | A note on the path cover number of regular graphs[END_REF][START_REF] Nakano | A time-optimal solution for the path cover problem on cographs[END_REF][START_REF] Ore | Arc coverings of graphs[END_REF][START_REF] Row | Zero forcing number, path cover number, and maximum nullity of cacti[END_REF][START_REF] Fatemeh | On the relationships between zero forcing numbers and certain graph coverings[END_REF][START_REF] Yu | Covering 2-connected 3-regular graphs with disjoint paths[END_REF] use the term "path cover" (or vertex-disjoint path cover) in the place of "path partition". Some authors use the term "decomposition" for "partition" [START_REF] Arumugam | Decomposition of graphs into paths and cycles[END_REF][START_REF] Rani | Induced path decomposition and hole in sierpinsky graph[END_REF].

A simple example in Figure 2 demonstrates the different behaviors of six different problems:

π c (G) = 1; ρ c (G) = 2; ip c (G) = 3; π p (G) = 1; ρ p (G) = 2; ip p (G) = 4; π c (H) = 2; ρ c (H) = 2; ip c (H) = 2; π p (H) = 3; ρ p (H) = 3; ip p (H) = 3;
The inequalities in Lemma 2.1 are true because of the following facts:

(1) An isometric path is an induced path. An induced path is a path.

(2) A path partition is a path cover. Lemma 2.1 For a given graph G,

(1) π c (G) ≤ ρ c (G) ≤ ip c (G); π p (G) ≤ ρ p (G) ≤ ip p (G); (2) π c (G) ≤ π p (G); ρ c (G) ≤ ρ p (G); ip c (G) ≤ ip p (G);
3 Some generalized concepts

In this section, we discuss some problems which are closely related to the six problems.

The k-path cover problem

A k-path is a path having at most k vertices. Here is a word of caution: While defining a k-path, some authors define k-path as a path of at most k vertices [START_REF] Jin | On the k-path cover problem for cacti[END_REF][START_REF]On the k-path partition of graphs[END_REF] and some authors define k-path as a path of length at most k [START_REF] Korpelainen | A boundary class for the k-path partition problem[END_REF]. Korpelainen [START_REF] Korpelainen | A boundary class for the k-path partition problem[END_REF] states that the 3-path partition problem is NP-complete on comparability graphs. According to his definition of k-path, the correct statement is that the 2-path partition problem is NP-complete on comparability graphs.

A k-path cover is a set of k-paths that cover V . The k-path cover problem is to find a k-path cover of minimum cardinality in G. This is a generalized version of path cover problem [START_REF]On the k-path partition of graphs[END_REF]. When k = 2, the k-path cover problem becomes the edge cover problem. It is straightforward to define other five problems in the same way [START_REF] Korpelainen | A boundary class for the k-path partition problem[END_REF][START_REF] Monnot | The path partition problem and related problems in bipartite graphs[END_REF][START_REF]On the k-path partition of graphs[END_REF].

The k-path partition problem is solved for trees [START_REF] Yan | Hedetniemi, k-path partitions in trees[END_REF], cacti [START_REF] Jin | On the k-path cover problem for cacti[END_REF], cographs for a fixed k [START_REF] Steiner | On the k-path partition problem in cographs[END_REF], threshold graphs [START_REF] Steiner | On the k-path partition problem in cographs[END_REF], bipartite permutation graphs [START_REF]On the k-path partition of graphs[END_REF]. The 3-path partition problem is NP-complete on general graphs [START_REF] Garey | Computers and Intractability: A guide to the theory of NP-completeness[END_REF] and comparability graphs [START_REF]On the k-path partition of graphs[END_REF]. The k-path partition problem is NP-complete on the class of cographs [START_REF] Steiner | On the k-path partition problem in cographs[END_REF] and chordal bipartite graphs [START_REF]On the k-path partition of graphs[END_REF] if k is part of the input. The k-path partition problem as well as the induced k-path partition problem remains NP-complete on bipartite graphs of maximum degree three [START_REF] Monnot | The path partition problem and related problems in bipartite graphs[END_REF]. The k-path partition problem remains NP-complete for a graph class defined by finitely many minimal forbidden induced subgraphs [START_REF] Korpelainen | A boundary class for the k-path partition problem[END_REF]. Korpelainen [START_REF] Korpelainen | A boundary class for the k-path partition problem[END_REF] has nicely analyzed the differences between the k-path cover problem and induced k-path cover problem. The author also provides a good account of literature survey on k-path cover problems and their related topics [START_REF] Korpelainen | A boundary class for the k-path partition problem[END_REF].

The S-path cover problem

Here is another generalization of the path cover problem. For a set S of vertices in a graph G = (V, E), an S-path cover is a path cover P in which every vertex of S is an endpoint of a path in P . The S-path cover problem is to find an S-path cover of minimum cardinality in G. Some authors [START_REF] Asdre | A linear-time algorithm for the kfixed-endpoint path cover problem on cographs[END_REF][START_REF]A polynomial solution to the k-fixed-endpoint path cover problem on proper interval graphs[END_REF][START_REF] Breeanne | The k-fixed-endpoint path partition problem[END_REF][START_REF] Li | A linear time algorithm for the 1-fixed-endpoint path cover problem on interval graphs[END_REF] call it k-fixed-endpoint path cover problem (or kP C problem) where k = |S|. Notice that, when S is empty, the S-path cover problem coincides with the classical path cover problem [START_REF] Yeh | The path-partition problem in bipartite distance-hereditary graphs[END_REF].

It is shown that the 1-Fixed-Endpoint path cover problem is polynomial on interval graphs [START_REF] Li | A linear time algorithm for the 1-fixed-endpoint path cover problem on interval graphs[END_REF] and the k-fixed-endpoint path cover problem is polynomial on cographs [START_REF] Asdre | A linear-time algorithm for the kfixed-endpoint path cover problem on cographs[END_REF], proper interval graphs [START_REF]A polynomial solution to the k-fixed-endpoint path cover problem on proper interval graphs[END_REF]. The S-path partition number is polynomially solvable for bipartite distance-hereditary graph [START_REF] Yeh | The path-partition problem in bipartite distance-hereditary graphs[END_REF]. The PhD thesis by Baker [START_REF] Breeanne | The k-fixed-endpoint path partition problem[END_REF] is a good source of information on this problem.

The k-path vertex cover problem

There is another concept in the literature called k-path vertex cover (which is denoted by k-(All-) Path Cover) [START_REF] Funke | On k-path covers and their applications[END_REF]. A set C of vertices is a k-path vertex cover if every k-path on k vertices contains at least one vertex from C [START_REF] Li | The k-path vertex cover in Cartesian product graphs and complete bipartite graphs[END_REF]. While the k-path cover problem is an extension of edge cover problem, the k-path vertex cover problem is an extension of vertex cover problem. Brause and Krivoš-Belluš [START_REF] Brause | On a relation between k-path partition and k-path vertex cover[END_REF] have studied the relationship between the k-path vertex cover problem and the k-path partition problem. Both these problems are completely different from the computational complexity point of view. The k-path vertex cover problem is NP-complete for cubic planar graphs of girth 3 for k = 3 [START_REF] Tu | The vertex cover P 3 -problem in cubic graphs[END_REF]. Funke, Nusser and Storandt [START_REF] Funke | On k-path covers and their applications[END_REF] have provided a list of applications of this problem on different domains.

A discussion on the Gallai-Milgram theorem

One of the earliest contributions to the path partition problem is the Gallai-Milgram theorem. While surveying the Gallai-Milgram theorem, Berge states that the Gallai-Milgram theorem has been independently extended by Las Vergnas and Linial [START_REF] Berge | Path partitions in directed graphs[END_REF][START_REF] Hartman | Variations on the Gallai-Milgram theorem[END_REF][START_REF]Berge's conjecture on directed path partitions -a survey[END_REF][START_REF] Linial | Covering digraphs by paths[END_REF]. The Gallai-Milgram theorem illustrates the differences among the three pathtypes such as path, induced path and isometric path. The Gallai-Milgram theorem is true only for path covers and path partitions in undirected graphs. Let α(G) denote the independence number of G. Notice that the inequalities in Theorem 4.3 are not true for trees. The following result is straightforward and does not require any proof: Theorem 4.4 Let G be an undirected bipartite graph. Then

ρ c (G) ≤ ρ p (G) ≤ α(G); ip c (G) ≤ ip p (G) ≤ α(G)
In undirected graphs, the Gallai-Milgram theorem illustrates how the behavior of isometric and induced paths changes from the dense graphs (such as chordal graphs without pendant vertices) to sparse graphs (such as bipartite graphs).

Following Las Vergnas and Linial, Berge takes the Gallai-Milgram theorem to the next level which is the famous Berge path partition conjecture [START_REF] Berge | Path partitions in directed graphs[END_REF][START_REF] Hartman | Variations on the Gallai-Milgram theorem[END_REF][START_REF]Berge's conjecture on directed path partitions -a survey[END_REF] and weak path partition conjecture [START_REF]Extending the greene-kleitman theorem to directed graphs[END_REF]. Hartman [START_REF]Berge's conjecture on directed path partitions -a survey[END_REF] has provided a survey on the Berge path partition conjectures.

As we have discussed the behavior of the Gallai-Milgram theorem on bipartite graphs and chordal graphs, a similar discussion on the Berge path partition conjecture will be interesting. It will also be useful to study the behavior of the Berge path partition conjecture for different path-types such as paths, induced paths, and isometric paths on special classes of undirected graphs.

The three cover problems

In this section, we shall discuss three problems: the path cover problem, the induced path cover problem and the isometric path cover problem.

The path cover problem

The Hamiltonian path problem, and hence the path cover problem is NP-complete for planar graphs, bipartite graphs, chordal graphs, chordal bipartite graphs, and strongly chordal graphs [START_REF] Yeh | The path-partition problem in bipartite distance-hereditary graphs[END_REF]. Lin, Olariu and Pruesse [START_REF] Lin | An optimal path cover algorithm for cographs[END_REF] have presented an optimal algorithm for determining a minimum path cover for cographs. Unfortunately, there is no record of any significant research work on the path cover problem. But there is a variant of path cover problem which is called the identifying path cover problem. A path cover P is an identifying path cover if for each pair u, v of vertices, there is a path P of P such that exactly either u or v belongs to P . Foucaud and Kovše [START_REF] Foucaud | Identifying path covers in graphs[END_REF] have given lower and upper bounds on the minimum size of an identifying path cover for general graphs and discuss the tightness of the bounds. They have also illustrated that any connected graph G has an identifying path cover of size at most 2|V |/3 + 5.

The induced path cover problem

The induced path cover problem is NP-complete for general graphs [START_REF] Garey | Computers and Intractability: A guide to the theory of NP-completeness[END_REF]. There is no record of any significant research work on the induced path cover problem too.

The isometric path cover problem

There may not be vast difference between paths and induced paths. But there is distinct difference between induced paths and isometric paths. The following problems illustrate the difference:

(1) The problem of finding an induced path between a vertex s and a vertex t containing a vertex v remains NP-complete in bipartite graphs [START_REF] Mezzini | On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs[END_REF]. However, the problem of finding an isometric path between a vertex s and a vertex t containing a vertex v is polynomially solvable for general graphs.

(2) Given a positive integer k, the problem of finding an induced path of length at least k is NP-complete [START_REF] Garey | Computers and Intractability: A guide to the theory of NP-completeness[END_REF]. However, the problem of finding an isometric path of length at least k is a trivial problem.

(3) The problem of deciding, given a graph G and two vertices s and t, whether there exists an induced path of given parity between s and t in G is NP-complete [START_REF] Kaminski | Finding an induced path of given parity in planar graphs in polynomial time[END_REF]. But the corresponding isometric problem is polynomially solvable.

Fitzpatrick [25] has introduced the concept of the isometric path cover problem in her PhD thesis [START_REF] Pan | Isometric path numbers of block graphs[END_REF]. The isometric path cover number is computed for tress, cycles, complete bipartite graphs, the Cartesian product of paths (including hypercubes) under some restricted cases [START_REF] Fisher | The isometric number of a graph[END_REF]25,[START_REF]The isometric path number of the cartesian product of paths[END_REF][START_REF] Shannon | Covering hypercubes by isometric paths[END_REF]. Fisher and Fitzpatrick [START_REF] Fisher | The isometric number of a graph[END_REF][START_REF] Shannon | Fractional isometric path number[END_REF] have derived a lower bound that ip c (G) ≥ |V |/(diam(G) + 1) and have shown that the isometric path cover number of an r × r grid is 2r/3 and the isometric path cover number of a tree with leaves is /2 . Fitzpatrick et al. [START_REF] Shannon | Covering hypercubes by isometric paths[END_REF] have shown that the isometric path number of hypercube Q r is at least 2r/(r + 1). In addition, they have also shown that ip c (Q r ) = 2 r-log 2 (r+1) when r + 1 is a power of 2. Pan and Chang have given a linear-time algorithm to solve the isometric path cover problem on block graphs [START_REF] Pan | Isometric path numbers of block graphs[END_REF], complete r-partite graphs and Cartesian products of 2 or 3 complete graphs [START_REF]Isometric path numbers of graphs[END_REF].

The strong geodetic problem is a variation of the geodetic problem which is to find a minimum set S of vertices of a graph G such that each vertex of G lies on some isometric path between a pair of vertices from S [START_REF] Harary | The geodetic number of a graph[END_REF]. A strong geodetic set of a graph G is a set S of vertices such that each vertex of G lies on a fixed isometric path between a pair of vertices from S [START_REF] Manuel | Strong geodetic problem in networks[END_REF]. For a graph G, its strong geodetic number sg(G) is the cardinality of a minimum strong geodetic set of G. The relationship between the isometric path cover number and the strong geodetic number is given below: Theorem 5.1 ( [START_REF] Manuel | Strong geodetic problem in networks[END_REF]) Let G be a graph.

(1) When G is an undirected graph,

1+ √ (8×ipc(G)+1) 2 ≤ sg(G) ≤ 2 × ip c (G).
(2) When G is a tree or block graph, ip c (G) = sg(G)/2 .

Even though the isometric path cover problem is a fundamental concept in graph theory, to our knowledge, there are no literatures on the computational complexity status of the isometric path cover problem for general graphs.

The three partition problems

In this section, we discuss the other set of three problems: the path partition problem, the induced path partition problem and the isometric path partition problem.

The path partition problem

The path partition problem was introduced by Ore in 1961 [START_REF] Ore | Arc coverings of graphs[END_REF]. The Hamiltonian path problem is NP-complete and hence the path partition problem is NP-complete for planar graphs, bipartite graphs, chordal graphs, chordal bipartite graphs, and strongly chordal graphs [START_REF] Yeh | The path-partition problem in bipartite distance-hereditary graphs[END_REF]. Nakano, Olariu and Zomaya [START_REF] Nakano | A time-optimal solution for the path cover problem on cographs[END_REF] call this problem as notoriously difficult and have reported an NC-algorithm to solve the path partition problem for cographs. Dinh [START_REF] Vu | Path partition number in tough graphs[END_REF] has studied the path partition problem for graphs with toughness greater than or equal to 1. Asdre, Nikolopoulos and Papadopoulos [START_REF] Asdre | An optimal parallel solution for the path cover problem on P 4 -sparse graphs[END_REF] have presented an optimal parallel algorithm for the path partition problem on P 4 -sparse graphs. Pan and Chang [START_REF] Pan | Path partition for graphs with special blocks[END_REF] have designed a linear-time algorithm for the path-partition problem in graphs whose blocks are complete graphs, cycles or complete bipartite graphs. The path-partition problem is polynomially solvable for forests [START_REF] Skupién | Path partitions for vertices and Hamiltonicity of graphs[END_REF], interval graphs [START_REF] Rao | Linear algorithm for optimal path problem on interval graphs[END_REF][START_REF] Chang | A certifying algorithm for the path cover problem on interval graphs[END_REF][START_REF]Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs[END_REF], circular arc graphs [START_REF] Hung | Solving the path cover problem on circulararc graphs by using an approximation algorithm[END_REF], distance-hereditary graphs [START_REF]Finding a minimum path cover of a distance-hereditary graph in polynomial time[END_REF], bipartite permutation graphs [START_REF] Srikant | Optimal path cover problem on block graphs and bipartite permutation graphs[END_REF], block graphs [START_REF] Pak | Optimal path cover problem on block graphs[END_REF][START_REF] Yan | The path-partition problem in block graphs[END_REF], cographs [START_REF] Chang | The L(2, 1)-labeling problem on graphs[END_REF], bipartite distance-hereditary graphs [START_REF] Yeh | The path-partition problem in bipartite distance-hereditary graphs[END_REF], co-comparability graphs [START_REF] Corneil | LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs[END_REF][START_REF] Kóhler | Linear time LexDFS on cocomparability graphs[END_REF]. Given a connected graph G, there is a spanning tree T of G such that π p (G) = π p (T ) [START_REF] Boesch | On covering the points of a graph with point disjoint paths, Graphs and Combinatorics[END_REF]. The relationship between the path partition number and L(2, 1)-labeling number of graphs have been studied by several authors [START_REF] Chang | The L(2, 1)-labeling problem on graphs[END_REF][START_REF] Lu | Path covering number and L(2, 1)-labeling number of graphs[END_REF].

Graffiti.pc conjecture

The number of edges in a maximum matching of a graph G is called the matching number of G, denoted by α (G). The total domination number of G, denoted by γ t (G), is a minimum set S of vertices such that every vertex of G is adjacent to some vertex in S. The Graffiti.pc conjectures are well-known for total domination number [START_REF] Delavińa | Some conjectures of graffiti.pc on total domination[END_REF]. Some of the conjectures are related to path partition number. DeLaViña et al. [START_REF] Delavińa | Some conjectures of graffiti.pc on total domination[END_REF] have positively answered to some Graffiti.pc conjectures which are related to path partition numbers.

Theorem 6.1 ([21]) For every graph G with no isolated vertex, γ t (G) ≤ α (G) + π p (G). When G is a connected 3-regular graph, γ t (G) ≥ 2π p (G).
Henning and Wash [START_REF] Henning | Matchings, path covers and domination[END_REF] have improved Graffiti.pc conjectures and shown that the bounds are tight.

Theorem 6.2 ([36]) If G is a graph of order n, then α (G) + (1/2)π p (G) ≥ (n/2). Moreover, when δ(G) ≥ 3, then γ t (G) ≤ α (G) + (1/2)(π p (G) -1).

Some bounds on the path partition number π p (G)

While introducing the path partition problem, Ore [START_REF] Ore | Arc coverings of graphs[END_REF] has produced the following bound: Theorem 6.3 ([59]) Given a graph G of order n, the path partition number π p satisfies π p (G) ≤ n-σ 2 (G), where σ 2 (G) is the minimum sum of degrees of two nonadjacent vertices.

According to Magnant and Martin [START_REF] Magnant | A note on the path cover number of regular graphs[END_REF], the above bound by Ore is sharp. There is another strong bound on the path partition number due to Hartman [START_REF] Hartman | Variations on the Gallai-Milgram theorem[END_REF]. The Gallai-Milgram theorem with respect to the path partition number which is π p (G) ≤ α(G) is improved by Hartman [START_REF] Hartman | Variations on the Gallai-Milgram theorem[END_REF] under certain conditions: Theorem 6.4 ( [START_REF] Hartman | Variations on the Gallai-Milgram theorem[END_REF]) Let G be a graph with connectivity k. If α(G) > k, then the path partition number satisfies π p (G) ≤ α(G) -k. [START_REF] Magnant | A note on the path cover number of regular graphs[END_REF] have posed the following conjecture: Conjecture 6.5 ([53]) Given a k-regular graph G of order n, the path partition number satisfies π p (G) ≤ n/(k + 1).

Magnant and Martin

The bound in the Conjecture 6.5 is sharp [START_REF] Magnant | A note on the path cover number of regular graphs[END_REF]. In support of their conjecture, they have provided the following result: Theorem 6.6 ( [START_REF] Magnant | A note on the path cover number of regular graphs[END_REF]) Given a k-regular graph G of order n with 0 ≤ k ≤ 5, the path partition number satisfies π p (G) ≤ n/(k + 1).

Magnant, Wang and Yuan [START_REF] Magnant | Path partitions of almost regular graphs[END_REF] have recently revised the Conjecture 6.5 as follows: Conjecture 6.7 ( [START_REF] Magnant | Path partitions of almost regular graphs[END_REF]) Given positive integers δ and ∆ with δ ≤ ∆, if G is a graph of order n with δ ≤ δ(G) ≤ ∆(G) ≤ ∆, then π p (G) ≤ max{n/(δ + 1), (∆ -δ)n/(∆ + δ)}.

They have also proved this conjecture when δ = 1, 2. They have also provided another bound as follows:

Theorem 6.8 ([54]) Suppose G is a graph of order n with ∆(G) = ∆ < 2δ = 2δ(G), then π p (G) ≤ ((∆ -2)n/(2(∆ + δ -4)).
While pointing out that Conjecture 6.5 is true even for k ≥ (n -1)/2, Han [START_REF] Han | On vertex-disjoint paths in regular graphs[END_REF] has provided a tight bound for bipartite graphs as follows: Theorem 6.9 ( [START_REF] Han | On vertex-disjoint paths in regular graphs[END_REF]) Given a bipartite k-regular graph G of order n, the path partition number satisfies π p (G) ≤ n/2k. For 3-regular graphs, Reed [START_REF] Reed | Paths, stars and the number three[END_REF] has provided a bound which is sharper than the bound in Conjecture 6.5. Theorem 6.10 ( [START_REF] Reed | Paths, stars and the number three[END_REF]) Given a connected 3-regular graph G of order n, the path partition number satisfies π p (G) ≤ n/9.

Reed [START_REF] Reed | Paths, stars and the number three[END_REF] also demonstrates that these results are tight. Furthermore, Reed has conjectured in the same paper that Conjecture 6.11 ([66]) Given a 2-connected 3-regular graph G of order n, the path partition number satisfies π p (G) ≤ n/10 . This conjecture has been recently settled by Yu [START_REF] Yu | Covering 2-connected 3-regular graphs with disjoint paths[END_REF]. In addition, Yu has given an interesting lower bound for π p (G): Theorem 6.12 ( [START_REF] Yu | Covering 2-connected 3-regular graphs with disjoint paths[END_REF]) There are infinitely many 2-connected 3-regular n-vertex graphs whose path cover numbers are at least n/14.

The induced path partition problem

Chartrand et al. [START_REF] Chartrand | The induced path number of bipartite graphs[END_REF] have introduced the concept of induced path partition problem and have produced the induced-path number of complete bipartite graphs, complete binary trees, 2-dimensional meshes, butterflies, and general trees. They have shown that ρ p (P m × P n ) = 2. In addition, they have also derived upper bounds for hypercubes and conjectured that ρ p (Q r ) ≤ r for the r-dimensional hypercube Q r with r ≥ 2 [START_REF] Chartrand | The induced path number of bipartite graphs[END_REF]. Alsardary [START_REF] Alsardary | The induced path number of the hypercube[END_REF] has answered to the conjecture that ρ p (Q r ) ≤ 16 [START_REF]Induced-path partition on graphs with special blocks[END_REF]. The induced path partition problem is concluded to be NP-complete by showing that it is NPcomplete to determine whether the vertex set of a graph can be partitioned into two induced paths [START_REF] Le | Splitting a graph into disjoint induced paths or cycles[END_REF]. Pan and Chang [START_REF]Induced-path partition on graphs with special blocks[END_REF] have presented a linear-time algorithm for the induced path partition problem on graphs whose blocks are complete graphs, cycles or complete bipartite graphs. Broere, Jonck and Domke [START_REF] Broere | The induced path number of the cartesian product of some graphs[END_REF]

have determined ρ p (G) for G = K m × K n and have shown that ρ p (C m × C n ) < 3.
Broere et al. [START_REF] Broere | The induced path number of the complements of some graphs[END_REF] have studied the induced path partition problem on the complements of some graphs such as cycles, paths, product of complete graphs, and product of cycles. They have also produced an elegant Nordhaus-Gaddum type relation in terms of induced path partition number ρ p as follows: (3) | | ≤ ρ p (T ) + ρ p (T ) ≤ 3(n -1)/2 for trees T where is the # of leaves of T .

Several authors [START_REF] Barioli | Zero forcing sets and the minimum rank of graphs[END_REF][START_REF] Hogben | Minimum rank problems[END_REF][START_REF] Perdigao | Minimum rank and path cover number for generalized and double generalized cycle star graphs[END_REF][START_REF] Row | Zero forcing number, path cover number, and maximum nullity of cacti[END_REF][START_REF] Fatemeh | On the relationships between zero forcing numbers and certain graph coverings[END_REF] have studied the relationship between the zeroforcing number z(G) and the induced path partition number ρ p (G). Hogben [START_REF] Hogben | Minimum rank problems[END_REF] have shown that ρ p (G) ≤ z(G) for general graphs. It is shown that ρ p (G) = z(G) when G is a block-cycle graph, unicyclic graph, double path, and series of double paths [START_REF] Fatemeh | On the relationships between zero forcing numbers and certain graph coverings[END_REF], a tree [START_REF] Barioli | Zero forcing sets and the minimum rank of graphs[END_REF] and a cactus [START_REF] Row | Zero forcing number, path cover number, and maximum nullity of cacti[END_REF].

Catral et al. [START_REF] Catral | Zero forcing number, maximum nullity, and path cover number of subdivided graphs[END_REF] have studied the induced path partition problem for edge subdivision graphs. Let e = uv be an edge of G. An edge subdivision graph G e is obtained from G by inserting a new vertex w into V , deleting the edge e and inserting edges uw and wv.

Let us recall that M (G) denotes the maximum nullity of G. Johnson and Duarte [START_REF] Johnson | The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree[END_REF] have shown that M (G) = ρ p (G) when G is a tree. Barioli, Fallat and Hogben [START_REF]On the difference between the maximum multiplicity and path cover number for tree-like graphs[END_REF] have proved that M (G) = ρ p (G) or M (G) = ρ p (G) -1 for unicyclic graphs. Sinkovic [START_REF] Sinkovic | Maximum nullity of outerplanar graphs and the path cover number[END_REF] have derived that M (G) ≤ ρ p (G) for any outerplanar graph G and M (G) = ρ p (G) for any partial 2-path G. Barioli, Fallat and Hogben [START_REF] Barioli | Computation of minimal rank and path cover number for certain graphs[END_REF] have studied the relationship between minimum rank and the induced path partition number and have derived that ∆(G) ≤ ρ p (G) where ∆(G) = max{p -q/ there are q vertices of G whose deletion leaves p induced paths}.

The isometric path partition problem

It is quite a big surprise that there is no literature on the isometric path partition problem including the computational complexity status of isometric path partition problem for general graphs.

Conclusion

This article is meant for young researchers in graph theory. It identifies the gaps and open space in "covering and partitioning by path-types" as potential research topics. Among all the six problems, the most attractive and interesting problem is path partition problem. The literatures on the path partition problem are larger than those of the other five problems. The reason may be due to the Gallai-Milgram theorem and Berges path partition conjecture. There are a very few literatures in path cover problem, induced path problem and isometric partition problem. Between the covering and partitioning problems, it is observed that researchers are more active on path-type partition problems than path-type cover problems.

In addition to the six problems, we have also considered several problems which are related to these six problems. We have also discussed the correlation among these six problems and their related problems. We have covered the literatures for the last 30 years.

Chang and his teammates have carried out significant research on paths [START_REF] Chang | The L(2, 1)-labeling problem on graphs[END_REF][START_REF] Pan | Path partition for graphs with special blocks[END_REF][START_REF] Yan | The path-partition problem in block graphs[END_REF][START_REF] Yan | Hedetniemi, k-path partitions in trees[END_REF][START_REF] Yeh | The path-partition problem in bipartite distance-hereditary graphs[END_REF], induced paths [START_REF]Induced-path partition on graphs with special blocks[END_REF] and isometric paths [START_REF] Pan | Isometric path numbers of block graphs[END_REF][START_REF]Isometric path numbers of graphs[END_REF]. Young researchers are encouraged to read these papers to understand how Chang and his teammates apply different techniques to solve different path-type problems.

We have discussed only vertex version of the covering and partitioning problems. The edge version of these problems is equally popular among the researchers. In the same way, covering and partitioning by cycles or trees are other well-known subtopics

Figure 1 :

 1 Figure 1: Six types of covering / partitioning problems

Figure 2 :

 2 Figure 2: Illustration how the six problems are different

Theorem 4 . 1 (

 41 Gallai-Milgram) Let P be a minimal path partition of an undirected graph G. Then there is an independent set S in G such that S contains exactly one vertex from each path in P . The vertex set V of G can be partitioned by at most α(G) paths.

Theorem 4 . 2 (

 42 Gallai-Milgram) Let G be an undirected graph. Then π c (G) ≤ π p (G) ≤ α(G).

Figure 3 :

 3 Figure 3: The Gallai-Milgram theorem fails for induced paths and isometric paths in undirected graphs

Theorem 6 .

 6 13 ([15]) Given an undirected graph on n vertices, (1) √ n ≤ ρ p (G) + ρ p (G) ≤ 3n/2 for arbitrary graph G (2) 1 + n/4 ≤ ρ p (G) + ρ p (G) ≤ 3n/2 for bipartite graph G.

Acknowledgment

The author expresses his deep gratitude to Prof Sandi Klavžar for his valuable contribution and encouragement. The author also thanks Prof Michael Henning and Prof Gexin Yu for their comments.

of research in graph theory.


Denis Serre
email: denis.serre@ens-lyon.fr

Multi-dimensional scalar conservation laws with unbounded integrable initial data

We discuss the minimal integrability needed for the initial data, in order that the Cauchy problem for a multi-dimensional conservation law admit an entropy solution. In particular we allow unbounded initial data. We investigate also the decay of the solution as time increases, in relation with the nonlinearity.

The main ingredient is our recent theory of divergence-free positive symmetric tensor. We apply in particular the so-called compensated integrability to a tensor which generalizes the one that L. Tartar used in one space dimension. It allows us to establish a Strichartz-like inequality, in a quasilinear context. This program is carried out in details for a multi-dimensional version of the Burgers equation.

Notations. When 1 ≤ p ≤ ∞, the natural norm in L p (R n ) is denoted • p , and the conjugate exponent of p is p . The total space-time dimension is d = 1 + n and the coordinates are x = (t, y). In the space of test functions, D + (R 1+n ) is the cone of functions which take non-negative values. The partial derivative with respect to the coordinate y j is ∂ j , while the time derivative is ∂ t . Various finite positive constants that depend only the dimension, but not upon the solutions of our PDE, are denoted c d ; they usually differ from one inequality to another one.

Introduction

Let us consider a scalar conservation law in 1 + n dimensions (1)

∂ t u + n ∑ i=1 ∂ i f i (u) = 0, t > 0, y ∈ R n .
We complement this equation with an initial data u(0, y) = u 0 (y), y ∈ R n .

The flux f (s) = ( f 1 (s), . . . , f n (s)) is a smooth vector-valued function of s ∈ R. We recall the terminology that an entropy-entropy flux pair is a couple (η, q) where s → η(s) is a numerical function, s → q(s) a vector-valued function, such that q (s) ≡ η (s) f (s). The Kruzhkov's entropies and their fluxes form a one-parameter family: η a (s) = |s -a|, q a (s) = sgn(ua) ( f (u)f (a)).

Together with the affine functions, they span the cone of convex functions.

We recall that an entropy solution is a measurable function u ∈ L 1 loc ([0, +∞) × R n ) such that f (u) ∈ L 1 loc ([0, +∞) × R n ), which satisfies the Cauchy problem in the distributional sense,

∞ 0 dt R n (u∂ t φ + f (u) • ∇ y φ) dy + R n u 0 (y)φ(0, y) dy = 0, ∀φ ∈ D(R 1+n ), (2)
together with the entropy inequalities

∞ 0 dt R n (η a (u)∂ t φ + q a (u) • ∇ y φ) dy + R n
η a (u 0 (y))φ(0, y) dy ≥ 0,

∀ φ ∈ D + (R 1+n ), ∀ a ∈ R. (3)
When it enjoys higher integrability, an entropy solution is expected to satisfy additional entropy inequalities of the form (4)

∞ 0 dt R n (η(u)∂ t φ + q(u) • ∇ y φ) dy + R n η(u 0 (y))φ(0, y) dy ≥ 0, ∀φ ∈ D + (R 1+n ),
for more general convex entropies η. In particular, one is interested in inequality (4) for the entropy-entropy flux pair

η(s) = 1 2 s 2 , q(s) = s 0 z f (z) dz.
The theory of this Cauchy problem dates back to 1970, when S. Kruzhkov [START_REF] Kružkov | First order quasilinear equations with several independent variables (in Russian)[END_REF] proved that if u 0 ∈ L ∞ (R n ), then there exists one and only one entropy solution in the class

L ∞ (R + × R n ) ∩C(R + ; L 1 loc (R n )).
The operator S t : u 0 → u(t, •), which maps L ∞ (R n ) into itself, enjoys several additional properties. On the one hand, a comparison principle says that if u 0 ≤ v 0 , then S t u 0 ≤ S t v 0 . For instance, the solution u associated with the data u 0 is majorized by the solution ū associated with the data (u 0 ) + , the positive part of u 0 . On another hand, if v 0u 0 is integrable over R n , then S t v 0 -S t u 0 is integrable too, and

(5)

R n |S t v 0 -S t u 0 |(y) dy ≤ R n |v 0 -u 0 |(y) dy.
Finally, if u 0 belongs to some L p (R n ) space, then S t u 0 has the same integrability, and the map t → S t u 0 p is non-increasing. We warn the reader that the contraction property (5) occurs only for the L 1 -norm, but not for other L p -norms.

Because of ( 5) and the density of

L 1 ∩ L ∞ (R n ) in L 1 (R n )
, the family (S t ) t≥0 extends in a unique way as a continuous semi-group of contractions over L 1 (R n ), still denoted (S t ) t≥0 . When u 0 ∈ L 1 (R n ) is unbounded, we are thus tempted to declare that u(t, y) := (S t u 0 )(y) is the abstract solution of the Cauchy problem for [START_REF] Ph | Regularizing effects of homogeneous evolution equations[END_REF] with initial data u 0 . An alternate construction of (S t ) t≥0 , based upon the Generation Theorem for nonlinear semigroups, is due to M. Crandall [START_REF] Crandall | The semigroup approach to first order quasilinear equations in several space variables[END_REF], who pointed out that it is unclear whether u is an entropy solution, because the local integrability of the flux f (u) is not guaranted. It is therefore an important question to identify the widest class of integrable data for which u is actually an entropy solution of (1).

To achieve this goal, we develop a new strategy, based on the Compensated Integrability that we introduced in our previous papers [START_REF] Serre | Divergence-free positive symmetric tensors and fluid dynamics[END_REF][START_REF] Serre | Compensated integrability. Applications to the Vlasov-Poisson equation and other models in mathematical physics[END_REF]. It uses a map a → M(a) ∈ Sym d , whose lines are entropy-entropy flux pairs, where the entropies are precisely the functions id R , f 1 , . . . , f n which appear in the conservation law. The map M is a non-decreasing function of a. This tensor was already used when n = 1 by L. Tartar [START_REF] Tartar | Compensated compactness and applications to partial differential equations[END_REF] to prove the compactness of the semi-group, and by F. Golse [START_REF] Golse | Hyperbolic problems: theory, numerics and applications[END_REF] (see also [START_REF] Golse | Optimal regularizing effect for scalar conservation laws[END_REF]) to prove some kind of regularity. An essential ingredient is the amount of non-linearity displayed by the flux f . We illustrate our strategy by carrying out the details on the most typical nonlinear conservation law, a multi-d generalization of the Burgers equation.

Outline of the article. We begin with a detailed, definitive, analysis of the multi-d Burgers equation. The equation is described in the next section. Our main result is a well-posedness when the initial data is integrable. It is based on a dispersion estimate, which has the flavour of a Strichartz inequality, from which we derive a decay estimate of L p -norms for p ≤ d 2 d-1 . The proof is given in Sections 3 and 4. We explain how the strategy extends to general fluxes f in Section 5.

Acknowledgements. I am indebted to C. Dafermos, whose precious comments helped me to improve this article, in particular in giving full credit to previous contributors. I also thank L. Silvestre for correcting a miscalculation.

The multi-d Burgers equation

For a conservation law of the general form [START_REF] Ph | Regularizing effects of homogeneous evolution equations[END_REF], it is harmless to assume f (0) = 0. By chosing an appropriate inertial frame, which does not affect the norms u(t) p , we may also assume f (0) = 0. Thus f (s) = O(s 2 ) at the origin. Say that f (s) ∼ s k v 1 as s → 0, where v 1 is a non-zero constant vector. We may perform a linear change of the spacial coordinates such that

f 1 (s) ∼ s k k and f j (s) = o(|s| k ) otherwise.
Unless we meet a flat component, he process can be continued until we find a new coordinate system (y 1 , . . . , y n ) in which

f j (s) ∼ s k j k j , 2 ≤ k 1 < k 2 • • • < k n .
Generically, we have k j = j + 1 for every j ∈ [ [1, n]]. This is the reason why we consider from now on the following scalar conservation law, which we call the multi-dimensional Burgers equation :

(6) ∂ t u + ∂ j u 2 2 + • • • + ∂ n u n+1 n + 1 = 0.
This particular flux was already considered by G. Crippa et al. [START_REF] Crippa | Regularizing effect of nonlinearity in multidimensional scalar conservation laws. Transport equations and multi-D hyperbolic conservation laws[END_REF]. If n = 1, we recognize the original Burgers equation. The equation ( 6) is a prototype for genuinely nonlinear conservation laws, those which satisfy the assumption

(7) det( f , . . . , f (n+1) ) = 0.
The latter condition is a variant of the non-degeneracy condition at work in the kinetic formulation of the equation (1) ; see [START_REF] Lions | A kinetic formulation of multidimensional scalar conservation laws and related equations[END_REF] or [START_REF] Perthame | Kinetic formulation of conservation laws[END_REF].

Let us review two preliminary answers to our natural question, in the context of [START_REF] Golse | Optimal regularizing effect for scalar conservation laws[END_REF].

• On the one hand, we might assume that u 0 ∈ L 1 ∩ L p (R n ) for some p > 1. Let us define

u 0m := max(-m, min(u 0 , m)) ∈ L 1 ∩ L ∞ (R n ),
which tends towards u 0 in the L 1 -norm. We have u = lim m→+∞ u m , where u m is the solution associated with the data u 0m , and the limit stands in

C b (R + ; L 1 (R n )). Because of u m (t) p ≤ u 0m p ≤ u 0 p , the sequence (u m ) m≥1 is bounded in L ∞ (R + ; L p (R n )). We infer that u ∈ L ∞ (R + ; L p (R n )), and u m converges towards u in L ∞ (R + ; L q (R n )) for every q ∈ [1, p). In addition, u m converges weakly in L ∞ (R + ; L p (R n )). If p > n + 1,
we may pass to the limit as m → +∞ in the sequences

u k m , sgn(u m -a)(u k m -a k ).
Passing to the limit in the integral formulations ( 2) and ( 3), we conclude that u is a genuine entropy solution of the Cauchy problem. Notice that the argument does not work out when p = n + 1, because of the last component of the flux: we are not certain that u n+1 m converges in L 1 loc towards u n+1 . If p > n + 2, we find as well that u satisfies the entropy inequality for the pair ( η, q). The drawback of this argument is that it does not exploit the nonlinearity of the equation, a property which is expected to imply some kind of regularization or dispersion (see Theorem 4 and Proposition 1 of [START_REF] Lions | A kinetic formulation of multidimensional scalar conservation laws and related equations[END_REF]). We should be able to lower somehow the threshold p > n + 1.

• The other answer concerns the one-dimensional case (n = 1). The Kruzhkov solution of the classical Burgers equation satisfies the inequality

(8) TV u(t) 2 2 ≤ 2 u 0 1 t ,
due to Bénilan & Crandall [START_REF] Ph | Regularizing effects of homogeneous evolution equations[END_REF], who exploit the homogeneity of the flux. It is extended by Dafermos [4] to situations where the flux f has an inflexion point and the data u 0 has bounded variations, by a careful use of the generalized backward characteristics. It implies in particular an estimate

(9) u(t) ∞ ≤ 2 2 u 0 1 t .
This shows that the assumption u 0 ∈ L 1 (R) is sufficient in order that u be a true entropy solution. This is definitely better than the threshold L 1 ∩L 2 (R n ) considered in the previous paragraph.

Dafermos' argument, which is the most general one, uses the ordered structure of the real line. Backward characteristics are not unique in general. Given a base point (x * ,t * ) in the upper half-plane, one has to define and analyse the minimal and the maximal ones. These notions have not yet been extended to the multi-dimensional situation (see however [START_REF] Silvestre | Oscillation properties of scalar conservation laws[END_REF] for a weaker notion).

Our main result here is the following statement. It tells us that L 1 (R n ) is the right space for initial data.

Theorem 2.1 (Multi-d Burgers equation.) Suppose u 0 ∈ L 1 (R n ). Define u(t) = S t u 0 and set u(t, y) = u(t)(y) for t > 0 and y ∈ R n . Then 1. There holds an algebraic decay:

(10) u(t) d 2 d-1 ≤ c d t -δ u 0 γ 1 ,
where

γ = d 2 + 1 d(d 2 -d + 2) , δ = 2 (d -1)(d 2 -d + 1) d 2 (d 2 -d + 2) < 1. 2. For every k ∈ [[1, d + 1]], there holds u k ∈ L 1 loc (R + × R n ).
3. The function u is an entropy solution of the Cauchy problem.

It satisfies the additional entropy inequality

∂ t η(u) + div y q(u) ≤ 0.

If in addition u

0 ∈ L 1 ∩ L d (R n ), then u ∈ L d 2 d-1 (R + × R n ) and there holds (11)
∞ 0 R n u d 2 d-1 dydt d-1 d ≤ c d R n u 0 (y) d dy 1 2 R n u 0 (y)dy 1 2
.

Comments.

• The assumption that u 0 ∈ L 1 (R n ) extends that available in the 1-dimension situation. However, when n = 1, Theorem 2.1 provides an estimate of u(t) in L 4 (R) only, instead of the known L ∞ (R) or BV (R). Our results are new only when n ≥ 2.

• The decay result is optimal when n = 1, where it states that

u(t) 4 ≤ cst • t -3/8 u 0 5/8 1 .
This is the exact rate for an N-wave

N L (t, y) = y 1+t if y ∈ (0, L √ 1 + t), 0 otherwise.
It raises therefore the question whether the decay rate given by ( 10) is accurate also when n ≥ 2.

• Estimate (11) ressembles a Strichartz inequality. It seems to be new in this situation where the principal part in not a linear operator, but a quasilinear one.

• By Hölder interpolation, together with u ∈ L ∞ (R + ; L 1 (R n )), (10) implies ( 12)

u(t) q ≤ c d,q t -κ/q u 0 1-ν/q 1 , ∀q ∈ (1, d 2 d + 1
),

where

κ = 2 d -1 d 2 -d + 2 and ν = d(d -1) d 2 -d + 2 .
• A natural question is whether (12) extends to every q ∈ [1, ∞]. In particular, is it true that u(t) ∈ L ∞ (R n ) for every t > 0 ? We now that it is true when n = 1, see [START_REF] Perthame | Kinetic formulation of conservation laws[END_REF].

• A useful contribution in this direction was obtained recently by L. Silvestre [START_REF] Silvestre | Oscillation properties of scalar conservation laws[END_REF], whose Theorem 1.5 tells in particular that if

u 0 ∈ L 1 ∩ L ∞ (R n ), then u(t) ∞ ≤ C( u 0 ∞ ; µ) u 0 µ 1 t -nµ
for every µ < µ 0 where

µ 0 = 2 d 2 -d + 2 .
This decay is almost the same as that suggested by extrapolation to q = ∞ of ours, because of nµ 0 = κ = κ q .

It would be exactly that one if the limit exponent µ 0 was allowed, and the dependency of the constant upon u 0 ∞ was removed.

Other "monomial" scalar conservation laws

As suggested above, we may be interested into more general conservation laws, whose fluxes are monomial. Denoting P k (s) = s k k , consider the PDE (13)

∂ t u + ∂ 1 P k 1 (u) + • • • + ∂ n P k n (u) = 0, where 1 < k 1 < • • • < k n are integers.
We leave, as a tedious exercise, the interesting reader to adapt the calculations of the two next sections to [START_REF] Tartar | Compensated compactness and applications to partial differential equations[END_REF], to prove the following result. We denote

K = n ∑ j=1 k j , N = 1 + 2K -n.
Theorem 2.2 Suppose that nk n < N. Then for every initial data u 0 ∈ L 1 (R n ), the abstract solution given by the continuous extension of the semi-group (S t ) t≥0 to L 1 (R n ), is actually an entropy solution of the Cauchy problem for [START_REF] Tartar | Compensated compactness and applications to partial differential equations[END_REF]. It satisfies a dispersion estimate

∞ 0 dt R n u(t, y) N n dy n n+1 ≤ c d R n u 0 (y)dy 1-θ R n u 0 (y) k n dy θ , where θ = K -n (n + 1)(k n -1)
.

It decays as follows

u(t) N n ≤ c d u 0 γ 1 t δ where γ = n N + N -n N(N -K) , δ = n(N -n) N(N -K) .
The rôle of the assumption nk n < N is to allow us to estimate u(t) k n in terms of u(t) 1 and u(t) N/n , in order to apply a Gronwall argument to the dispersion estimate. Notice that it is always satisfied in one space dimension, because then 1

• k 1 < N = 2k 1 Remark. If k n is larger than N
n , there should be a weaker result. There will be some exponent

p = p(k n , N) ∈ (1, k n ) such that if u 0 ∈ L 1 ∩ L p (R n ),
then the abstract solution is actually an entropy solution. We leave the calculation of p(k n , N) to the motivated reader.

3 Proof of Estimate [START_REF] Serre | Compensated integrability. Applications to the Vlasov-Poisson equation and other models in mathematical physics[END_REF] Because u is obtained as the limit in C(R + ; L 1 (R n )) of u m , the solution associated with the data u 0m = Proj [-m,m] u 0 , the estimates ( 10) and ( 11) need only to be proved when the initial data belongs to L 1 ∩ L ∞ (R n ), that is within Kruzhkov's theory. Then they extend to L 1 -data by a density argument.

When

u 0 ∈ L 1 ∩ L ∞ , (11) will provide a uniform bound of ∞ 0 u m (t) d 2 d-1 d 2 d-1 dt.
Then, because of u m → u in C(R + ; L 1 (R n )) as m → +∞, we infer by interpolation that the convergence holds true in every space L q (R + ; L p (R n )) for which

1 ≤ p < d 2 d -1 (equivalently d 2 d -1 < q ≤ ∞) and d -1 p + d 2 -d + 1 q = d -1.
Because of (S t u 0 ) ± ≤ S t (u 0 ) ± , it is enough to consider data that are either non-negative or non-positive. But since v(t, y) = -u(t, -y 1 , y 2 , . . . , (-1) n y n ) is the entropy solution associated with v 0 (y) = -u 0 (-y 1 , y 2 , . . . , (-1) n y n ), it suffices to prove [START_REF] Serre | Compensated integrability. Applications to the Vlasov-Poisson equation and other models in mathematical physics[END_REF] for non-negative data and solutions. We therefore assume from now on that u 0 ≥ 0, and thus u ≥ 0 over R + × R n .

If a ∈ R, we define a symmetric matrix M(a) = a i+ j+1 i + j + 1 0≤i, j,≤n .

Remarking that

M(a) = a 0 V (s) ⊗V (s) ds, V (s) =    1 . . . s n    ,
we obtain that M(a) is positive definite whenever a > 0. We have obviously

det M(a) = H d a d 2 ,
where

H d = 1 i + j + 1 0≤i, j,≤n > 0
is the determinant of the Hilbert matrix (this is the only case where we do not write c d for a dimensional constant).

Let us form the symmetric tensor

T (t, y) = M(u(t, y)),
with positive semi-definite values. Its first line is formed of (u, f (u)) and therefore is divergencefree by [START_REF] Golse | Optimal regularizing effect for scalar conservation laws[END_REF]. The second line is formed of ( η(u), q(u)), an entropy-flux pair. It is not divergencefree in general, although it is so away from shock waves and other singularities of the solution u. But the entropy inequality tells us that the opposite of its divergence if a non-negative, hence bounded measure,

µ 1 = -div t,y ( η(u), q(u)) ≥ 0.
The total mass of µ 1 over a slab (0, τ) × R n is given by

µ 1 = R n η(u 0 (y)) dy - R n η(u(τ, y)) dy ≤ R n η(u 0 (y)) dy.
Notice that the latter bound does not depend of τ. The same situation occurs for the other lines of T . They are of the form (η(u), q(u)) where (η, q) is an entropy-flux pair with η convex over R + (recall that u takes only non-negative values). The distribution

µ = -div t,y (η(u), q(u))
is therefore again a bounded measure, whose total mass over R + × R n is bounded by

R n η(u 0 (y)) dy.
We conclude that the row-wise divergence of T is a (vector-valued) bounded measure, whose total mass is bounded above by

d ∑ j=2 R n u 0 (y) j j dy.
We may therefore apply Compensated integrability (Theorems 2.2 and 2.3 of [START_REF] Serre | Compensated integrability. Applications to the Vlasov-Poisson equation and other models in mathematical physics[END_REF]) to the tensor T , that is

τ 0 dt R n (det T ) 1 d-1 dy ≤ c d T 0• (0, •) 1 + T 0• (τ, •) 1 + Div t,y T M ((0,τ)×R n ) d d-1 .
Because of

T 0• (t, •) 1 ≤ d ∑ j=1 R n u(t, y) j j dy ≤ d ∑ j=1 R n u 0 (y) j j dy,
We recast (15) as

Y 1 β + c d u 0 α β 1 Y ≤ 0.
Multiplying by Y -1/β and integrating, we infer (mind that 1 -1 β is negative)

t + c d u 0 α β 1 Y (0) 1-1 β ≤ c d u 0 α β 1 Y (t) 1-1 β .
This provides a first decay estimate

Y (t) ≤ c d u 0 α 1-β 1 t -β 1-β .
Remarking that t → X(t) is a non-increasing function, so that

τ 2 X(τ) ≤ Y ( τ 2 ),
we deduce the ultimate decay result

X(t) ≤ c d u 0 α 1-β 1 t -1 1-β .
Restated in terms of a Lebesgue norm of u(t), it says

(16) u(t) d 2 d-1 ≤ c d u 0 γ 1 t -δ ,
where

γ = d 2 + 1 d(d 2 -d + 2) , δ = 2 (d -1)(d 2 -d + 1) d 2 (d 2 -d + 2) .

The function u is an entropy solution

We already know that the functions u m are entropy solutions, with initial data

u 0m ∈ L 1 ∩L ∞ (R n ).
Because of [START_REF] Serre | Compensated integrability. Applications to the Vlasov-Poisson equation and other models in mathematical physics[END_REF], we have seen that u m converges towards u in the norm of L q (R + ; L p (R n )) whenever

1 ≤ p < d 2 d -1 and d -1 p + d 2 -d + 1 q = d -1. Because of d 2 d-1 > d + 1, this implies that (u m ) k → u k for every k ∈ [[1, d + 1]]. Recalling that f (s) = (s, s 2 2 , . . . , s d d
) and q(s) = ( s 3 3 , . . . ,

s d+1 d + 1 ),
we see that we may pass to the limit as m → +∞ in the identity

∞ 0 dt R n (u m ∂ t φ + f (u m ) • ∇ y φ) dy + R n u 0m (y)φ(0, y) dy = 0, ∀φ ∈ D(R 1+n ),
as well as in the Kruzhkov inequalities

∞ 0 dt R n (η a (u m )∂ t φ + q a (u m ) • ∇ y φ) dy + R n η a (u 0m (y))φ(0, y) dy ≥ 0, ∀φ ∈ D + (R 1+n ),
and in the inequality

∞ 0 dt R n ( η(u m )∂ t φ + q(u m ) • ∇ y φ) dy + R n η(u 0m (y))φ(0, y) dy ≥ 0, ∀φ ∈ D + (R 1+n ).
Therefore u is an entropy solution with initial data u 0 , which satisfies in addition the entropy inequality for the pair ( η, q).

Remark. When n ≥ 2, the Compensated Integrability cannot be applied directly to the solution u, when the data is only integrable. Because we don't know whether the jth line of T is locally integrable if j = 3, • • • , n + 1 ; its last component is u n+ j n+ j , where the exponent n + j is larger than d 2 d-1 .

The strategy for general fluxes f

We come back to the study of a multi-dimensional conservation law of general form (1). Following the ideas develloped in the Burgers case, we begin by considering a signed, bounded initial data:

u 0 ∈ L 1 ∩ L ∞ (R n ), u 0 ≥ 0. If a ∈ R + , we define a symmetric matrix M(a) = a 0 F (s) ⊗ F (s) ds,
where F(s) = (s, f 1 (s), . . . , f n (s)). This matrix is positive definite under the non-degeneracy condition that F([0, a]) is not contained in an affine hyperplane. We denote

∆(a) := (det M(a)) 1 n ≥ 0. Let us define T (t, y) := M(u(t, y)). Because u ∈ L ∞ (0, τ; L 1 ∩ L ∞ (R n ))
, the tensor T is integrable over (0, τ) × R n . The first line of T is divergence-free. The other lines are made of entropy-entropy flux pairs ( f i , Q i ). Since f i might not be convex, we cannot estimate the measure µ i = -∂ t f i (u)div y Q i (u) directly by the integral of f i (u 0 ). To overcome this difficulty, we define a convex function φ over R + by

φ(0) = φ (0) = 0, φ (s) = | f (s)|. Remark that | f | ≤ φ and | f | ≤ φ.
Let Φ be the entropy flux associated with the entropy φ. Then the measure ν := -∂ t φ(u)div y Φ(u) is non-negative and a bound of its total mass is as usual

ν ≤ R n φ(u 0 (y)) dy.
We now use the kinetic formulation of (1), a notion for which we refer to [START_REF] Perthame | Kinetic formulation of conservation laws[END_REF], Theorem 3.2.1. Recall the definition of the kinetic function χ(ξ; a), whose value is sgn a if ξ lies between 0 and a, and is 0 otherwise. There exists a non-negative bounded measure m(t, y, ξ) such that the function g(t, y, ξ) = χ(ξ; u(t, y)) satisfies

∂ t g + f (ξ) • ∇ y g = ∂ ∂ξ m, g(0, y; ξ) = χ(ξ; u 0 (y)).
If (η, q) is an entropy-entropy flux pair, then the measure µ = -∂ t ηdiv y q is given by

µ = R η (ξ)dm(ξ).
We deduce that the vector-valued measure µ = (µ 1 , . . . , µ n ) satisfies |µ| ≤ ν. This yields the estimate µ ≤ R n φ(u 0 (y)) dy.

We may therefore apply the compensated integrability, which gives here To improve the inequality above, we use again a scaling argument. However, because the components f j of the flux are not homogeneous anymore, we modify simultaneously the solution and the flux, using the fact that the constant c d in (17) does not depend upon f . Our new The symmetric matrix N(a) that plays the role of M(a) for ( 18) is given by the formula N(s) = λ RM(λs)R T , R = diag( 1 λ , P -1 ).

We have det N(s) = λ n-1 (det P) -2 det M(λs), from which we derive

∞ 0 R n (det N(v)) 1 n dy dt = λ -1 n (det P) -1-2 n ∞ 0 R n ∆(u) dy dt.
When applying (18) to v and g, one integral in the right-hand side transforms easily: The other one involves a modified function φ λ,P (s) = ψ P (λs), ψ P (s) = |P -1 f (s)|.

As usual ψ P is fixed by ψ P (0) = ψ P (0) = 0. We have therefore

1 n.

 1 (t, y)) dy ≤ c d F(u 0 ) 1 + F(u(τ)) 1 + R n φ(u 0 (y)) dy 1+ Because of | f | ≤ φ and φ(u(τ)) 1 ≤ φ(u 0 ) 1 ,we end up with an analog of (11) t, y))dy ≤ c d ( u 0 1 + φ(u 0 ) 1 ) 1+ 1 n .

  where P ∈ GL n (R) is a matrix to be chosen later. The function v is an entropy solution of the Cauchy problem associated with the conservation law∂ t v + div y g(v) = 0for the flux (18) g(s) = P -1 f (λs).

= 1 λ

 1 det P R n u 0 (y) dy.

φ 1 n

 1 P (v 0 (y)) dy = 1 det P R n ψ P (u 0 (y)) dy.All the identities above, together with (18) applied to (v, g), yield our parametrized estimate∞ 0 R n ∆(u) dy dt ≤ c d λ

.

The only bad feature in the estimate ( 14) is the lack of homogeneity of its right-hand side. To recover a well-balanced inequality, we exploit an idea already used in [START_REF] Serre | Divergence-free positive symmetric tensors and fluid dynamics[END_REF]. We begin by remarking that if λ > 0 is a constant parameter, then the function

is the entropy solution associated with the initial data

Applying (14) to the pair (v, v 0 ) instead, then using

, we get a parametrized inequality

In order to minimize the right-hand side, we choose the value

The extreme terms, for j = 1 or d, contribute on a equal foot with

The other ones, which are

R n u j 0 dy, are bounded by the same quantity, because of Hölder inequality. We end therefore with the fundamental estimate [START_REF] Serre | Compensated integrability. Applications to the Vlasov-Poisson equation and other models in mathematical physics[END_REF].

Proof of Theorem 2.1

We now complete the proof of our main theorem.

The decay result

We keep working with the assumptions

From the Hölder inequality, we have

The inequality [START_REF] Serre | Compensated integrability. Applications to the Vlasov-Poisson equation and other models in mathematical physics[END_REF] implies therefore

.

Considering the solution v(t, y) = u(t + τ, y), whose initial data is u(τ, •), we also have (15

We optimize this inequality with respect to λ, by choosing

There remains to minimize the right-hand side with respect to P :

where

The calculation of I[w] has to be made on a case-by-case basis.

Let us define again

Applying (19) on an interval (τ, ∞) instead, and using the decay of the L 1 -norm, we arrive to A decay result will be obtained through a Gronwall argument, whenever we can estimate I[u(t)] in terms of u(t) 1 and X(t).