Polynomial Treedepth Bounds in Linear Colorings
Jeremy Kun Michael P. O'Brien Marcin Pilipczuk Blair D. Sullivan

	Sufficient variable screening  via directional regression with censored response
    Menghao Xu^1, Zhou Yu^1, Jun Shao^1,2

	^1 School of Statistics, East China Normal University, Shanghai, China 

	^2Department of Statistics, University of Wisconsin-Madison, WI, 53706, USA
    December 30, 2023
=================================================================================================================================================================================================


	Low-treedepth colorings are an important tool for algorithms that exploit structure in classes of bounded expansion; they guarantee subgraphs that use few colors have bounded treedepth.
	These colorings have an implicit tradeoff between the total number of colors used and the treedepth bound, and prior empirical work suggests that the former dominates the run time of existing algorithms in practice.
	We introduce p-linear colorings as an alternative to the commonly used p-centered colorings.
	They can be efficiently computed in bounded expansion classes and use at most as many colors as p-centered colorings.
	Although a set of k<p colors from a p-centered coloring induces a subgraph of treedepth at most k, the same number of colors from a p-linear coloring may induce subgraphs of larger treedepth.
	We establish a polynomial upper bound on the treedepth in general graphs, and give tighter bounds in trees and interval graphs via constructive coloring algorithms.
	We also give a co-NP-completeness reduction for recognizing p-linear colorings and discuss ways to overcome this limitation in practice.
	arxivThis preprint extends results that appeared in <cit.>; for full proofs omitted from <cit.>, see previous versions of this preprint.Some of these results appeared previously in <cit.>.

	


	

§ INTRODUCTION

Algorithms for graph classes that exhibit bounded expansion structure <cit.> offer a promising framework for efficiently solving many NP-hard problems on real-world networks.
The structural restrictions of bounded expansion, which allow for pockets of localized density in globally sparse graphs, are compatible with properties of many real-world networks such as clustering and heavy-tailed degree distributions.
Moreover, multiple random graph models designed to mimic these properties have been proven to asymptotically almost surely belong to classes of bounded expansion <cit.>.
From a theoretical perspective, graphs belonging to classes of bounded expansion can be characterized by low-treedepth colorings of bounded size, i.e. using only a small number of colors.
Roughly speaking, a low-treedepth coloring is one in which the subgraphs induced on each small set of colors have small treedepth, a structural property stronger than treewidth.
This definition naturally implies an algorithmic pipeline <cit.> for classes of bounded expansion involving four stages:  computing a low-treedepth coloring, using the coloring to decompose the graph into subgraphs of small treedepth, solving the problem efficiently on each such subgraph, and combining the subsolutions to construct a global solution.
The complexities of algorithms using this paradigm often are of the form O(k  p 2^dlog d· n^c) where k is the coloring size and d is the treedepth of the subgraphs.

A recent implementation <cit.> and experimental evaluation <cit.> of this pipeline has identified that the coloring size has a much larger effect on the run time than the treedepth in practice.
Although graphs in classes of bounded expansion are guaranteed to admit colorings of constant size with respect to the number of vertices, the only known polynomial-time algorithms for computing these colorings are approximations <cit.>.
Consequently it is unclear to what extent our current coloring algorithms can be altered to reduce the coloring size.
A more viable approach to improving the performance of the algorithmic pipeline without significant high-level changes would be to develop a new type of low-treedepth coloring that uses fewer colors but potentially has weaker guarantees about the treedepth of the subgraphs.

The traditional low-treedepth colorings for classes of bounded expansion are known as p-centered colorings.
This name stems from the property that on any subgraph H, a p-centered coloring either uses at least p colors or is a centered coloring, which restricts the multiplicity of colors in induced subgraphs.
In this paper we introduce an alternative that closely mirrors this paradigm but only extends the color multiplicity guarantees to path subgraphs.
For this reason we refer to them as p-linear colorings and linear colorings.
We identify that p-linear colorings share three important properties with p-centered colorings that allow them to be used in the bounded expansion algorithmic pipeline.

	
  * The minimum coloring size is constant in graphs of bounded expansion.
	
  * A coloring of bounded size can be computed in polynomial time.
	
  * Small sets of colors induce graphs of small treedepth.

The third of these properties is of particular interest, since understanding the tradeoffs between coloring size and treedepth in switching between p-centered and p-linear colorings fundamentally depends on bounding the maximum treedepth of a graph that admits a linear coloring with k colors.
Equivalently, we frame this problem as determining the gap between the minimum number of colors needed for a linear versus a centered coloring in any given graph.
Using a grid minors approach, we prove that the minimum size of a centered coloring is polynomially bounded in the minimum size of a centered coloring.
Because the “heavy machinery” of this approach likely does not give a tight bound, we give stronger upper bounds on the gap in trees and interval graphs and a matching lower bound for binary trees.
Surprisingly, we also prove that some p-linear colorings cannot be verified in polynomial time unless P = co-NP and discuss the practical implications of these findings.
Some results in this paper appeared previously in WG 2018 <cit.>.
This version adds a polynomial treedepth upper bound for general graphs, as well as tighter lower and upper bounds for trees.

	

§ DEFINITIONS AND BACKGROUND

In this section we detail the background and terminology necessary to understand p-linear colorings.



 §.§ Graph Terminology

	We denote the vertices and edges of a graph G as V(G) and E(G), respectively, and assume all graphs are simple and undirected except where specifically noted otherwise.
	The open neighborhood of a vertex v, denoted N(v), is the set of vertices u such that uv∈ E(G), while the closed neighborhood, N[v] is defined as N(v)∪{v}.
	Vertex a is an apex with respect to a subgraph H if V(H) ⊆ N(a).

	We say P is a v_1v_ℓ-path if V(P) = {v_1,…, v_ℓ} for distinct v_1,…, v_ℓ and E(P) = {v_iv_i+1 : 1≤ i ≤ℓ-1}; we will notate this as P=v_1,…, v_ℓ.
	Given disjoint paths P = v_1,…, v_ℓ and Q = u_1,…, u_ℓ', the path P· Q = v_1,…, v_ℓ, u_1,…, u_ℓ' is the concatenation of P and Q if v_ℓ and u_1 are adjacent.
	A path is Hamiltonian with respect to subgraph H if V(P) = V(H).

	In a rooted tree T, we let T_v be the subtree of T rooted at v and the leaf paths of T_v be the set of paths from a leaf of T_v to v.
	We label the levels of T from bottom to top starting from 1; that is, if D is the maximum distance from a leaf to the root then the root is the only vertex in level D+1 and level i consists of all vertices whose parents are in level i+1.
	Vertices u and v are unrelated in T if u is neither an ancestor nor a descendant of v.

	A coloring ϕ of a graph G is a mapping of the vertices of G to colors 1,…, k and has size |ϕ|=k.
	A coloring is proper if no pair of adjacent vertices have the same color.
	For any subgraph H and color c, if there is exactly one vertex v∈ H such that ϕ(v) = c we say c appears uniquely in H and v is a center of H.
	A subgraph with no unique color is said to be non-centered.

	We use the notation X = Y_1⊎…⊎ Y_ℓ to denote that Y_1,…, Y_ℓ form a partition of X; that is, X = Y_1∪…∪ Y_ℓ and the sets Y_1,… Y_ℓ are pairwise disjoint.



 §.§ p-Centered Colorings and Bounded Expansion

	
		A p-centered coloring ϕ of graph G is a coloring such that for every connected subgraph H, H has a center or ϕ|_H uses at least p colors.
	
	and Ossana de Mendez established that bounding the minimum size of a p-centered coloring is a necessary and sufficient condition for a graph class to have bounded expansion.
	
		A class of graphs 𝒞 has bounded expansion iff there exists a function f such that for all G∈𝒞 and all p≥ 1, G admits a p-centered coloring with f(p) colors.
	
	There are varying methods to compute p-centered colorings, such as transitive-fraternal augmentations <cit.> and generalized coloring numbers <cit.>, we focus here on distance-truncated transitive-fraternal augmentations (DTFAs) <cit.>, which iteratively augment the graph with additional edges to impose constraints on proper colorings.
	This linear time algorithm guarantees that after (2log p)^p DTFA iterations, any proper coloring of the augmented graph is a p-centered coloring whose size is  bounded in classes of bounded expansion.



 §.§ Centered Colorings and Treedepth

	Note that if ϕ is a p-centered coloring of G and H is a subgraph of G whose vertices use at most p-1 colors in ϕ, H must have a center.
	This relates p-centered colorings to a more restricted class of graphs defined by centered colorings.
	
		A centered coloring ϕ of graph G is a coloring such that every connected subgraph has a center.
		The minimum size of a centered coloring of G is denoted (G).
	
	Note that a centered coloring is also proper, or else there would be a connected subgraph of size two with no center.
	Observe that if X is the set of all centers of G, then G\ X must either be empty or disconnected.
	This implies that if |G|≫(G), then G breaks into many components after only a few vertex deletions.
	This property is captured by treedepth decompositions.
	
		A treedepth decomposition 𝒯 of graph G is a rooted forest with the same vertex set as G such that uv∈ E(G) implies u is an ancestor of v in 𝒯 or vice versa.
		The depth of 𝒯 is the length of the longest path from a leaf of 𝒯 to the root of its component.
		The treedepth of G, (G), is the minimum depth of a treedepth decomposition of G.
	

	Given a centered coloring of size k, we can generate a treedepth decomposition of depth at most k by choosing any center v to be the root and setting the children of v to be the roots of the treedepth decompositions of the components of G\{v}.
	Likewise, given a treedepth decomposition of depth k, we can generate a centered coloring using k colors by bijectively assigning the colors to levels of the tree and coloring vertices according to their level.
	We refer to the colorings and decompositions resulting from these procedures as canonical; together they imply that the treedepth and centered coloring numbers are equal for all graphs.



§ P-LINEAR AND LINEAR COLORINGS

	We introduce p-linear colorings as an alternative to p-centered colorings.
	
		A p-linear coloring is a coloring ψ of a graph G such that for every path[This includes non-induced paths.] P, either P has a center or ψ|_P uses at least p colors.
	
	It is proven in <cit.> that after performing 2^p DTFA iterations, any proper coloring of the augmented graph is a p-linear coloring.
	This implies that p-linear colorings indeed have constant size in bounded expansion classes and can be constructed in polynomial time (like p-centered colorings).

	In the interest of maintaining consistency with prior terminology, we define linear colorings analogously to centered colorings.
	
		A linear coloring is a coloring ψ of a graph G such that every path has a center.
		The linear coloring number is the minimum number of colors needed for a linear coloring and is denoted (G).
	
	Note that linear colorings must also be proper.
	A simple recursive argument shows that every path of length d requires at least log_2(d+1) colors in a linear coloring; thus a graph of linear coloring number k has no path of length 2^k.
	Because every depth-first search tree is a treedepth decomposition, (G) ≤ 2^(G), proving that small numbers of colors in p-linear colorings induce graphs of bounded treedepth[This tightens a bound in <cit.> from double to single exponential.].

	Our study of the divergence between linear and centered coloring numbers will naturally focus on linear colorings that are not also centered colorings.
	We say ψ is a non-centered linear coloring (NCLC) of graph G if G contains a connected induced subgraph with no center.
	For NCLC ψ, we say a connected induced subgraph H is a witness to ψ if H is non-centered but every proper connected subgraph of H has a center.
	For the sake of completeness, we prove in Lemma <ref> that many simple graph classes do not admit NCLCs.
	
		If G is a cograph, has maximum degree 2, or has independence number 2, any linear coloring of G is also a centered coloring.
	
	
		We analyze each graph class separately below.

		Maximum degree 2:
			Let G be a graph of maximum degree 2.
			Each connected induced subgraph of G is either a path or a cycle, both of which have a Hamiltonian path.
			Thus every connected subgraph has a center, making any linear coloring centered.

			Cographs:
			Let ψ be an NCLC of cograph G and H be a witness to ψ.
			If ψ|_H only contains one color, H is an isolated vertex and the coloring is centered.
			Thus, we may assume ψ|_H has at least two colors.
			Because H is a cograph, we can partition its vertices into nonempty sets X, Y such that xy is an edge in H for all x∈ X and y∈ Y.
			But since ψ is proper, every pair of vertices with the same color must lie in the same set X or Y.
			Since every color in ψ|_H appears at least twice, there are vertices {v,v'}∈ X and {u,u'}∈ Y such that ψ(v) = ψ(v') and ψ(u) = ψ(u') but ψ(v)≠ψ(u).
			But then v,u,v'u' form a path with no center and thus ψ is not a linear coloring.

			Independence number 2:
			Since independence number is hereditary, it is sufficient to show every connected graph of independence number 2 has a Hamiltonian path.
			We prove this by induction on the number of vertices, observing that an isolated vertex has a trivial Hamiltonian path.
			Let G be a graph of independence number 2 and v∈ G a vertex such that G∖{v} is connected, e.g., v is a leaf in a minimum spanning tree of G.
			If G∖{v} has a Hamiltonian cycle, then G must have a Hamiltonian path.
			Otherwise, by the inductive hypothesis G∖{v} has a Hamiltonian path whose endpoints are some non-adjacent pair of vertices u,w.
			Either v is adjacent to one of u, w, in which case G has a Hamiltonian path, or {u, w, v} form an independent set of size 3.
	
	The classes described in Lemma <ref> are maximal in the sense that there are graphs with independence number 3 (graph R_3 described in Lemma <ref>) and binary trees (Lemma <ref>) that admit NCLCs.

	

§ TREEDEPTH LOWER BOUNDS

To understand the tradeoff between the number of colors and treedepth of small color sets when using p-linear colorings in lieu of p-centered colorings, it is important to know the maximum treedepth of a graph of fixed linear coloring number k, (k).
In Lemmas <ref> and <ref>, we prove lower bounds on (k) through explicit constructions of graph families.
In order to show that these graphs have large treedepth, we first establish assumptions about the structure of treedepth decompositions that can be made without loss of generality.

	Let G be a graph and S⊂ V(G) such that G[S] is connected and with respect to some component C∈ G\ S, every vertex in S is an apex of C.
	Then for any treedepth decomposition 𝒯 of G with depth k, we can construct a treedepth decomposition 𝒯' such that:
	
		
  * depth(𝒯') ≤ k
		
  * Each vertex in S is an ancestor of every vertex in C in 𝒯'
		
  * For each pair of vertices {u,w}⊆ V(C) or {u,w}⊆ V(G∖ C), u is an ancestor of w in 𝒯' iff it is an ancestor of w in 𝒯.
	


	
	
	Let ϕ be a canonical centered coloring of G with respect to 𝒯.
	Let 𝒯' be a canonical treedepth decomposition with respect to ϕ; if there are multiple vertices of unique color, prioritize removing those outside C before members of C, and then small colors over large colors, i.e., remove color 2 before color 5.
	Since 𝒯' is derived from a centered coloring with k colors, its depth is at most k, satisfying condition 1.

		Condition 2 is satisfied as long each member of S is removed in the construction of 𝒯' before any member of C.
	Note that since S contains apex vertices with respect to C and every vertex v∈ V(C) satisfies N[v]⊆ V(C)∪ V(S), the removal of any vertex from C cannot disconnect a previously connected component if S has not been removed.
	Thus at any point in the algorithm before the removal of S if a vertex in C has a unique color in its remaining component H, there must be another vertex in H\ C of unique color as well.
	Consequently, we will never be forced to remove any vertex of C before S.

		To prove condition 3 is satisfied, observe that u is an ancestor of w in 𝒯' iff there is a connected subgraph H containing u and w and no vertex with color smaller than ψ(u).
	As stated previously, G\ C is a connected subgraph, which means that there is a subgraph witnessing this ancestor-descendant relationship between u and w such that H∩ C = ∅ if u∉ C and H∩ (G\ C) = ∅ if u∈ C.
	Thus the relationships in 𝒯 are preserved in 𝒯'.



Using Lemma <ref>, we now show that (k)≥ 2k.

	There exists an infinite sequence of graphs R_1,R_2,… such that
	
    lim_i→∞(R_i)/(R_i) = 2.



	Define R_i recursively such that R_0 is the empty graph and R_i is a complete graph on vertices v_1,…, v_i along with i copies of R_p for p=⌊i-1/2⌋, call them H_1,…, H_i, such that v_j is an apex with respect to H_j (Figure 1).
	We prove that (R_i) = i and lim_i→∞(R_i) = 2i.

		With respect to the linear coloring number, note that (R_i)≥ i since the clique of size i requires i colors by Lemma <ref>.
	We prove the upper bound (R_i)≤ i by induction on i.
	The case of i=1 is trivial; assume it is true for 1,…, i-1.
	From the inductive hypothesis, we can assume each H_j only requires p colors for a linear coloring.
	Consider the coloring ψ of R_i such that ψ(v_j) = j and ψ|_H_j is a linear coloring of H_j using colors {1+(j+1) i, 1+(j+2) i,…, 1+(j+p) i}.
	If ψ is not a linear coloring, there is some path Q without a center.
	Since ψ(v_j)∉ψ|_H_j, Q must contain vertices from at least two H_js; each v_j is a cut vertex, so Q cannot contain vertices from more than two H_js.
	However, ψ^-1(1)⊆{v_1}∪ V(H_2) ∪…∪ V(H_p+1), but {2,…, p+1}∉ψ|_H_1, which means Q∩ H_1 = ∅.
	Based on the symmetry of ψ we can apply the same argument to the remaining colors, which means that no such non-centered path Q exists and ψ is indeed a linear coloring of size i.

		With respect to the centered coloring number, by Lemma <ref> there is an minimum-depth treedepth decomposition in which v_j is an ancestor of H_j.
	This implies there is a j such that no vertex in H_j shares a color in the canonical coloring with any of the vertices in the clique.
	Thus (R_i) = i + (R_p); in the limit this recursion approaches 2i.


The graphs in Lemma <ref> contain large cliques.
We now show that this is not a necessary condition for the linear and centered coloring numbers to diverge.

	Let B_ℓ be the complete binary tree with ℓ levels.
	Then
	
    lim_ℓ→∞(B_ℓ)/(B_ℓ)≥log_2 3.




Fix an integer a ≥ 1 and let b be the smallest integer such that

    2^a < 3^b.

Our proof proceeds by first constructing a coloring pattern Ψ_a of B_a and then using Ψ_a to create a linear coloring for an arbitrarily large complete binary tree.
Some vertices of B_a will be left uncolored (we will call them local), while some vertices will be colored with one of
the b colors [b] (we will call these colors global).
Let C_1,C_2,…,C_2^b be the sequence of all subsets of [b] in order of nonincreasing size (in particular, C_1 = [b] and C_2^b = ∅)
  and let ℓ be such that ∑_i=1^ℓ 2^|C_i|-1 = 2^a-1. Note that such an index ℓ exists due to Equation (<ref>):
 
    ∑_i=1^2^b 2^|C_i|-1 = 1/2· 3^b > 2^a-1

 and the fact that the sets C_i are ordered in the nonincreasing order of their sizes. Furthermore, we have ℓ < 2^b.

Let v_1,v_2,…,v_2^a-1 be an ordering of the leaves of B_a corresponding to an in-order traversal.
Consider an index 1 ≤ i ≤ℓ. By construction, there exists a vertex v_i∈ B_a at level |C_i| that is the root of a subtree T_v_i whose leaves are exactly v_j for ∑_i'=1^i-1 2^|C_i'|-1 < j ≤∑_i'=1^i 2^|C_i'|-1.
We color the vertices of T_v_i level by level with (global) colors of C_i; that is, we order the colors of C_i arbitrarily
and color level k of T_v_i with the k-th color of C_i for every k ∈ [|C_i|].
All remaining vertices of B_a (that is, those that lie in none of the subtrees T_v_i for 1 ≤ i ≤ℓ) remain local.

The following claim summarizes the properties of the above coloring.

For every path P in B_a
that either


  * has both endpoints in a leaf or the root of the tree B_a, or

  * does not contain a local vertex,

there exists a global color c ∈ [b] such c appears uniquely on P.


If a path P does not contain a local vertex, then it is contained in a single tree T_v_i.
For such a path, the unique vertex on P of maximum level
  is colored with a global color that appears uniquely on P.
Similarly, if P is a leaf path in B_a, then any globally colored vertex
of the tree T_v_i containing the leaf endpoint of P satisfies the desired property.
Otherwise, a path P that has both endpoints in leaves of B_a but contains a local vertex needs
to start in a leaf of one subtree T_v_i and end in a leaf of a different subtree T_v_i'.
Then, observe that any (global) color of C_i  C_i' appears exactly once on P.


Let p < 2^a be the number of local vertices in the pattern Ψ_a.
For an even integer d ≥ 2, consider a coloring ψ of B_ad defined as follows.
Fix a palette [db] of global colors and a palette [2p] of local colors.
For every 1 ≤ i ≤ d, the i-th stripe consists
of a levels (i-1)a+1,…,ia.
In B_ad, such a stripe consists of 2^(d-i)a copies of B_a.
Color every such copy using the pattern Ψ_a
with global colors (i-1)b+1, …, ib
as the b global colors of Ψ_a and color each local vertex with a different local
color from the set {1,2,…,p} if i is odd and from the set {p+1,p+2,…,2p}
if i is even.

We claim that the above is a linear coloring of B_ad with db+2p < db+2^a+1 colors.
Consider a path P in B_ad and let i be the index of the highest stripe
intersected by P.
By the choice of i, P intersects exactly one of the copies of B_a in the i-th stripe.
If P contains a leaf-to-leaf path in this copy, then Claim <ref> asserts
that P contains a center in this copy (recall that every stripe uses a different
    set of b global colors).
Otherwise, P intersects at most one copy of B_a in every stripe.
If P intersects at least three stripes, then P contains a root-to-leaf path
in the single copy of B_a intersected by P at stripe (i-1), and we are
again done by Claim <ref>.
Similarly, Claim <ref> finishes the proof if P does not contain a local
vertex at the i-th stripe.
Finally, in the remaining case P intersects at most two stripes (the i-th one
and possibly the (i-1)-th one) and contains a local vertex in the i-th stripe.
Since we used different set of local colors for odd and even stripes, any such local
vertex in i-th stripe is a center of P.

Consequently, we have exhibited a linear coloring of B_ad with less than db+2^a+1
colors, where b is defined as in Equation (<ref>). If we let d go to ∞, then
the ratio (ad)/(db+2^a+1) approaches a/b. This ratio, in turn, approaches
log_2(3) as a →∞ due to the choice of b at Equation (<ref>).
This finishes the proof of the lemma.



In Section <ref> we show that the bound in Lemma <ref> is tight for binary trees (Theorem <ref>).
We conjecture that the construction in Lemma <ref> is also tight for general graphs.

	For any graph G, (G)≤ 2(G).

While the exclusion of a path of length 2^k indicates (k) ≤ 2^k, this nonetheless leaves a large gap between the upper and lower bounds on (k).
To move towards a proof of Conjecture <ref>, we establish a polynomial upper bound on (k) in general graphs in the next section (Theorem <ref>).
Because this proof uses “heavy machinery”, we consider two restricted graph classes—namely, trees and interval graphs—in Sections <ref> and <ref> and give tighter upper bounds on (k) for graphs in these classes.

	

§ TREEDEPTH UPPER BOUNDS ON GENERAL GRAPHS

This section is devoted to proving a polynomial upper bound on (k).

	There exists a polynomial p such that every graph G satsifies
  ≤^190 p(log).


Our starting point is the following theorem of Kawarabayashi and Rossman <cit.>:

There is an absolute constant C such that every graph G
of treedepth at least C k^5 log^2 k satisfies at least one of the following:


  * the treewidth of G is at least k;

  * G contains a complete binary tree of height k as a minor;

  * G contains a path on 2^k vertices.


Assume that the treedepth of G is at least C k^5 log^2 k.
If G contains a path on 2^k vertices (condition 3), then clearly (G) ≥ k.
If G contains a complete binary tree of height k as a minor (condition 2), then G
also contains a subdivision of a complete binary tree of height k as a subgraph.
Since (H) ≤(G) for any subgraph H of G,
Theorem <ref> asserts that (G) ≥ k / log_2(3).
Thus, in the proof of Theorem <ref>, we are left with the
case when G has large treewidth.

Here, we use the celebrated grid minor theorem, with the best known bound due to Chuzhoy <cit.>.

	There is a polynomial p' such that every graph G with treewidth
	at least k^19 p'(log k) contains a k × k grid as a minor.

We slightly relax the notion of a k × k grid minor to a k-pseudogrid, defined as follows.

	A graph G contains a k-pseudogrid if there exist two sequences of vertex-disjoint
	paths in G, 𝒫 = (P_1,P_2,…,P_k)
	and 𝒬 = (Q_1,Q_2,…,Q_k) such that
	
		
  * for every i ∈ [k], the path P_i is a concatenation of paths P_i,0, P_i,1^Q, P_i,1, P_i,2^Q, P_i,2, …, P_i,k^Q, P_i,k in this order such that each path P_i,j^Q for j ∈ [k] is a subpath of Q_j (possibly consisting of a single vertex) and every
		path P_i,j, 0 ≤ j ≤ k does not contain any edge nor internal vertex on any path Q_j
		(we explicitly allow P_i,0 and P_i,k to be paths of length 0);
		
  * a symmetric condition holds with the roles of 𝒫 and 𝒬 swapped.
	


In what follows, the paths P_i,j, P_i,j^Q, Q_i,j, and Q_i,j^P are considered empty for pairs of indices (i,j) not defined above.

Clearly, if G contains a k × k-grid as a minor, it contains a k-pseudogrid:
just let the paths 𝒫 follow the rows of the grid and the paths of 𝒬 follow the columns.
To finish the proof of Theorem <ref>, it suffices to show the following technical
result.

If G contains a k-pseudogrid, then (G) = Ω(√(k)).


Fix a linear coloring ψ of G.
Let (𝒫, 𝒬) be a k-pseudogrid in G.
Let V(𝒫) = ⋃_P ∈𝒫 V(P) and similarly define V(𝒬).
Let μ(𝒫) be the number of distinct colors ψ uses on V(𝒫) and similarly define μ(𝒬).
To prove the lemma, it suffices to show for any k-pseudogrid (𝒫,𝒬) in G,
   k ≤ 100 · (μ(𝒫) + μ(𝒬))^2.
We shall prove it by induction over k.

The statement is trivial for k ≤ 100.
For an inductive step, we proceed as follows.
For a vertex v ∈ V(𝒫) ∪ V(𝒬), the grid coordinate of v is (i,j) if v ∈ V(P_i,j^Q) ∪ (V(P_i,j) ∖ V(P_i,j+1^Q)) ∪ V(Q_i,j^P) ∪ (V(Q_i,j) ∖ V(Q_i+1,j^P)).
A vertex v is marginal if its grid coordinates (i,j) satisfy i ≤ 3, j ≤ 3, i ≥ k-2, or j ≥ k-2.
A color c is infrequent on 𝒫 if it appears on V(𝒫), but there exists a family 𝒫_c ⊆𝒫
of at size at most 50(μ(𝒫) + μ(𝒬)) such that every vertex v ∈ V(𝒫) with ψ(v) = c is either marginal
or lies on one of the paths in 𝒫_c.
The definition of a color infrequent on 𝒬 is analogous.

For an inductive step, it suffices to show that there is always an infrequent color on 𝒫 or an infrequent color on 𝒬.
Indeed, assume that c is infrequent on 𝒫 (the arguments for 𝒬 are symmetrical) and let 𝒫_c ⊆𝒫 be as in the above definition.
Construct a k'-pseudogrid (𝒫',𝒬') from (𝒫,𝒬) as follows.
Start with (𝒫',𝒬') = (𝒫,𝒬). First, delete from 𝒫' the first and last 3 paths, and similarly
for 𝒬'. Second, shorten every path P_i ∈𝒫' by deleting the edges of P_i,j and P_i,j^Q for j ≤ 3 and j ≥ k-2;
similarly shorten every path Q_j ∈𝒬'. Finally, delete all (shortened) paths of 𝒫_c from 𝒫', and delete a matching number
of paths from 𝒬'.
In this manner, we obtain a k'-pseudogrid (𝒫',𝒬') such that
    k-k' ≤ 6 + 50(μ(𝒫) + μ(𝒬)) and such that the color c no longer appears on V(𝒫).
Therefore, μ(𝒫') + 1 ≤μ(𝒫) and μ(𝒬') ≤μ(𝒬).
The inductive step follows.

In the remainder of the proof, assume that there is no infrequent color on 𝒫 nor an infrequent color on 𝒬.
We shall reach a contradiction
by exhibiting a simple noncentered path P⊆𝒫∪𝒬.

We perform the following selecting and marking scheme. Initially, no vertex is selected and no path is marked.
For every color c that appears on V(𝒫), perform the following operation twice.

	
  *  Pick a vertex v ∈ V(𝒫) such that ψ(v) = c, v is not marginal,
	  and v does not lie on a marked path P_i. Let the grid coordinates of v be (i,j).
	
  *  Select v and mark all paths P_i' for |i'-i| ≤ 10 and all paths Q_j' for |j'-j| ≤ 10.

Now swap the roles of 𝒫 and 𝒬 and perform the above operation twice also for every color c that appears on V(𝒬).
In total, we select 2(μ(𝒫) + μ(𝒬)) vertices. For every selected vertex we mark 21 paths of 𝒫 and 21 paths of 𝒬.
Since there is no infrequent color, there is always a vertex to choose at Step <ref>, as otherwise the so-far marked paths would witness infrequency of c.
Thus, the above selecting and marking scheme is well-defined.

Let v,v' be two distinct selected vertices and let (i,j) and (i',j') be their grid coordinates. By the above marking scheme, we have that

    3 < i,i',j,j' < k-2   and   |i-i'| + |j-j'| ≥ 11.


Consider now the following simple path P. We start with P being the concatenation of even-numbered paths P_i without the prefixes and suffixes P_i,0∪ P_i,k in the natural order,
connected by paths Q_i,1∪ Q_i+1,1^P ∪ Q_i+1,1 for i divisible by 4 and by Q_i,k∪ Q_i+1,k^P ∪ Q_i+1,k for i≡ 2  4
(so that paths P_i with i≡ 2  4 are traversed forwards and paths P_i with i divisible by 4 are traversed backwards).
Then, for every selected v with grid coordinates (i,j), we pick an even i' ∈{i,i+1} and modify locally P ∩ P_i' to pass through v.
In the modification, we use only parts of paths P_i,j^Q ∪ P_i,j∪ P_i,j+1^Q, P_i+1,j^Q ∪ P_i+1,j∪ P_i+1,j+1^Q,
Q_i,j^P ∪ Q_i,j∪ Q_i+1,j^P, and Q_i,j+1^P ∪ Q_i,j+1∪ Q_i+1,j+1^P.
By Equation (<ref>), two such modifications do not interfere with each other and no such modification interferes with the connections contained in paths Q_1 and Q_k.
Consequently, the final path P is a simple path contained in 𝒫∪𝒬 that visits all selected vertices.
Such a path does not contain a center, which is the desired contradiction.


	

§ TREEDEPTH UPPER BOUNDS ON TREES

proved that there is a linear time algorithm for finding a minimum-sized centered coloring of a tree T <cit.>.
In this section we prove the following theorem by showing a correspondence between the centered coloring from algorithm and colors on paths in any linear coloring of T.

Let T be a tree of maximum degree Δ≥ 3,
Then algorithm finds a centered coloring of T
with size at most (log_2 Δ) ·(T).



In particular, for trees of maximum degree 3 we have (T) ≤log_2(3) (T),
   matching the lower bound of Lemma <ref>.
We do not have any matching lower bound for larger Δ.
In fact, we conjecture that none exists,
   that is, the upper bound of Theorem <ref> for Δ≥ 4 is not tight.

algorithm finds a particular centered coloring whose colors are ordered in a way that reflects their roles as centers.
For this reason, the coloring is called a vertex ranking and the colors are referred to as ranks; it guarantees that in each subgraph, the vertex of maximum rank is also a center.
We will use this terminology in this section to clearly distinguish between the ranks in the vertex ranking and colors in the linear coloring.
Note that the canonical centered coloring of a treedepth decomposition is a vertex ranking if the colors are ranked decreasing from the root downwards, which implies that every centered coloring can be converted to a vertex ranking of the same size.
Of central importance to algorithm are what we will refer to as rank lists.-1

	For a vertex ranking r of tree T, the rank list of T, denoted L(T), can be defined recursively as L(T) = L(T\ T_v)∪{r(v)} where v is the vertex of maximum rank in T.

algorithm arbitrarily roots T and builds the ranking from the leaves to the root of T, computing the rank of each vertex from the rank lists of each of its children.
For brevity, we denote L(v) = L(T_v) for every v in T.

	Let r be a vertex ranking of T produced by algorithm and let v∈ T be a vertex with children u_1,…, u_ℓ.
	If x is the largest integer appearing on rank lists of at least two children of v (or 0 if all such rank lists are pairwise disjoint) then r(v) is the smallest integer satisfying r(v)> x and r(v)∉⋃_i=1^ℓ L(u_i).

We root T at an arbitrary leaf of T and let r be a ranking output by Schaffers algorithm
applied on (rooted) T.
With a vertex v in T we associate the following potential.

    ζ(v) = ∑_r ∈ L(v) 2^r.

The following is immediate from Proposition <ref>:

For every v in T with children u_1,u_2,…,u_ℓ, it holds that

    ζ(v) ≤ 2 + ∑_i=1^ℓζ(u_i).

Furthermore, the equality holds if and only if all rank lists L(u_i) are pairwise disjoint.


Let ψ be a linear coloring of T with k := (T) colors.
Our proof of Theorem <ref> is based on tracking sets of colors of ψ on paths terminating at the current vertex as algorithm moves up the rooted tree.
Given a path P⊆ T and a linear coloring ψ of size k, we say a color set X⊆{1,…, k} is compatible with P if both the following conditions are true:

	
  * For every center v∈ P, ψ(v)∈ X.
	
  * For every color c∈ X, there is a vertex u∈ P such that ψ(u) = c.

In other words, a compatible set must not contain colors not found on P, must contain each color appearing uniquely in P, and may or may not contain any colors appearing multiple times on P.
For each v∈ T, let S(v) be a set of sets defined recursively as follows.
If v is a leaf, S(v) = {{ψ(v)}}.
Otherwise, let u_1,…, u_ℓ be the children of v, S' = ⋃_i=1^ℓ S(u_i), and ξ: S'→ 2^[k] be an injective function such that

    ξ(X) =
    	
    		X∖{ψ(v)}   if ψ(v)∈ X  and  X\{ψ(v)}∈ S' 
    
    		X∪{ψ(v)}   otherwise

for all X∈ S'.
Then S(v) = {ξ(X): X∈ S'}∪{{ψ(v)}}.
We start with the following straightforward observation.

For every v ∈ T it holds that ∅∉ S(v).
Consequently, for every nonleaf v ∈ T,
  ξ is a bijection between S' and S(v) ∖{{ψ(v)}}.

We prove that the construction of S(v) preserves compatibility of sets.

	For all vertices v∈ T and each X∈ S(v), there is a corresponding path P⊆ T_v with v as an endpoint such that P is compatible with X.


	It is clear that the lemma holds at the leaves of T, so we proceed by inductively showing the recursive step preserves the property.
  Observe that the path consisting of v only is compatible with {ψ(v)}∈ S(v).
  For any X∈ S(v) ∖{{ψ(v)}}, there is a child u of v such that X' = ξ^-1(X) is in S(u).
	By the inductive hypothesis, there must be a path P' terminating at u such that X' is compatible with P'.
	We claim that P = P'·{v} is compatible with X.
	Since X X'⊆{ψ(v)} and each color c≠ψ(v) appears the same number of times in P and P', it is only necessary to prove the requirements for compatibility are satified with respect to ψ(v).
	Moreover, because ψ(v) appears at least once on P it suffices to show that if ψ(v)∉ X, then ψ(v) appears multiple times on P.
	By the definition of ξ, ψ(v)∉ X implies ψ(v) ∈ X' and thus v is not a center of P.


Define ρ(v) = ∑_X∈ S(v) (Δ-1)^|X|.
We observe the following

	For any vertex v ∈ T with children u_1,…, u_ℓ,
  ρ(v)≥ (Δ-1) + ∑_i=1^ℓρ(u_i).


First, note that ℓ≤Δ-1.
Also, the lemma is straightforward for a leaf v as then S(v) = {{ψ(v)}} and
ρ(v) = Δ-1. Assume then ℓ≥ 1.

Recall that S' = ⋃_i=1^ℓ S(u_i).
Let S_1 be the set of all color sets that appear in exactly one S(u_i) and S_M be those that occur in multiple S(u_i)'s; we have S' = S_1 ⊎ S_M.
Note that for each X∈ S_M, ψ(v)∉ X or else concatenating the corresponding compatible paths with v creates a path with no center.
Likewise, if there are distinct color sets Y and Y' = Y\{ψ(v)} such that {Y,Y'}⊆ S_1∪ S_M, then Y,Y' both belong to the same S(u_i);
in particular, both Y,Y' belong to S_1.

By the definition of ξ, for each color set X∈ S(v) ∖{{ψ(v)}}
either |X| ≥ |ξ^-1(X)| or |X|  = |ξ^-1(X)| - 1.
In the latter case, there is a corresponding color set X' = X∪{ψ(v)} such that X'∈ S(v) and ξ^-1(X') = X. Also, from the discussion in the previous paragraph we infer
that this latter case can only happen when X,X' ∈ S_1.
Hence,

    ∑_X' ∈ S_1 (Δ-1)^|ξ(X')|   ≥∑_X' ∈ S_1 (Δ-1)^|X'|, and
    ∑_X' ∈ S_M (Δ-1)^|ξ(X')|   = (Δ-1) ∑_X' ∈ S_M (Δ-1)^|X'|.


We infer that

    ρ(v)    = (Δ-1)^|{ψ(v)}| + ∑_X ∈ S(v) ∖{{ψ(v)}} (Δ-1)^|X|
       = (Δ-1) + ∑_X' ∈ S' (Δ-1)^|ξ(X')|
       = (Δ-1) + ∑_X' ∈ S_1 (Δ-1)^|ξ(X')| + ∑_X' ∈ S_M (Δ-1)^|ξ(X')|
       ≥ (Δ-1) + ∑_X' ∈ S_1 (Δ-1)^|X'| + (Δ-1)∑_X' ∈ S_M (Δ-1)^|X'|
       ≥ (Δ-1) + ∑_i=1^ℓ∑_X' ∈ S(u_i) (Δ-1)^|X'|
       ≥ (Δ-1) + ∑_i=1^ℓρ(u_i).


We conclude with the proof of Theorem <ref>.


For every leaf v ∈ T, we have ρ(v) = Δ-1 ≥ 2 = ζ(v).
Lemmas <ref> and <ref> show inductively
that ρ(v) ≥ζ(v) for every v ∈ T.
If k' is the size of the centered coloring output by algorithm, then
for the root v_0 of T we have

    2^k'≤ζ(v_0) ≤ρ(v) ≤∑_X ⊆ [k] (Δ-1)^|X| = Δ^k.

Thus k' ≤ (log_2 Δ) · k.


	

§ TREEDEPTH UPPER BOUNDS ON INTERVAL GRAPHS

	Because linear colorings are equivalent to centered colorings when restricted to paths, we turn our attention to the linear coloring numbers of “pathlike” graphs.
	We investigate a particular class of “pathlike” graphs in this section and prove a quadratic relationship between their centered and linear coloring numbers.
	
		A graph G is an interval graph if there is an injective mapping f from V(G) to intervals on the real line such that uv∈ E(G) iff f(u) and f(v) overlap.
	
	We refer to the mapping f as the interval representation of G.
	Since the overlap between intervals f(u) and f(v) is independent of the interval representations of the other vertices, every subgraph of an interval graph is also an interval graph.
	The interval representation of G implies a natural “left-to-right” layout that gives it the “pathlike” qualities, which are manifested in restrictions on the length of induced cycles (chordal) and paths between vertex triples (AT-free).
	
		A graph is chordal if it has no induced cycles of length ≥ 4.
	
	
		Vertices u,v,w are an asteroidal triple (AT) if there exist uv-, vw-, and wu-paths P_uv, P_vw, and P_wu, respectively, such that N[w]∩ P_uv = N[u]∩ P_vw = N[v]∩ P_uv = ∅.
		A graph with no AT is called AT-free.
	
	
		A graph G is an interval graph iff G is chordal and AT-free.
	
	Intuitively, Definition <ref> is a set of three vertices such that every pair is connected by a path that avoids the neighbors of the third.
	Roughly speaking, in the context of linear colorings, Proposition <ref> indicates that if w is a center of a “long” uv-path P in G, any vertex w' such that ψ(w) = ψ(w') must have a neighbor on P.
	We devote the rest of this section to proving Theorem <ref>.
	
		There exists a polynomial time algorithm that takes as input an interval graph G and a linear coloring of G with size k and outputs a centered coloring of G with size at most k^2.
	
	Our algorithm makes extensive use of the following well-known property of maximal cliques in interval graphs.
	
		If G is an interval graph, its maximal cliques can be linearly ordered in polynomial time such that for each vertex v, the cliques containing v appear consecutively.
	
	In particular, we identify a prevailing path in G whose vertices “span” the maximal cliques and a prevailing subgraph that consists of the prevailing path as well as vertices in maximal cliques “between” consecutive vertices on the prevailing path.
	We will show that any linear coloring is a centered coloring when restricted to the prevailing subgraph and that after removing the prevailing subgraph, the remaining components each use fewer colors.

	Let C_1, … C_m be an ordering of the maximal cliques of G that satisfies Proposition <ref>.
	We say vertex v is introduced in C_i if v∈ C_i but v∉ C_i-1, and denote this as I(v) = i.
	Likewise, v is forgotten in C_j if v∈ C_j but v∉ C_j+1, and denote this as F(v) = j.
	The procedure for constructing a prevailing subgraph and prevailing path is described in Algorithm <ref>.
	This algorithm selects the vertex v from the current maximal clique that is forgotten “last” and adds v to the prevailing path and C_F(v) to the prevailing subgraph.
	We prove in Lemma <ref> that if P,Q are a prevailing path and subgraph, the vertices in Q\ P can be inserted between vertices of P to form a Hamiltonian path of Q.-1
	


	
		Every prevailing subgraph has a Hamiltonian path.
	
	
	Let P,Q be the prevailing path and subgraph constructed in Algorithm <ref>.
	We prove by constructing the Hamiltonian path of Q.
		
		Let M_j be the set of all u∈ Q\ P, for which j is the smallest integer for which u∈ C_F(v_j).
		In other words M_j contains the vertices in C_F(v_j) that do not appear in C_F(v_j-1).
		If ℳ =  ⋃_1≤ j≤ p M_j then by construction P∪ℳ = Q.
		Moreover, for each u∈ M_j, M_j∪{v_j,v_j+1}⊆ N[u].
		For each M_j, let μ^1_j,μ^2_j,…, μ^|M_j|_j be a ordering of M_j such that F(μ^i_j) ≤ F(μ^i+1_j).
		Then
			
    v_1,μ^1_1,…, μ^|M_1|_1, v_2,μ^1_2,…,μ^|M_2|_2, …, v_p,μ^1_p,…μ^|M_p|_p

		 is a Hamiltonian path.
	

	Although the fact that the prevailing subgraph Q has a Hamiltonian path implies Q has a center with respect to ψ, we must ensure that the proper subgraphs of Q also have a center.
	In Lemma <ref>, we prove ψ|_Q is centered by showing every proper connected subgraph of Q also has a Hamiltonian path.

	
		If Q is a prevailing subgraph of an interval graph G and ψ a linear coloring of G, ψ|_Q is a centered coloring.
	
	
		It suffices to show that every proper, connected induced subgraph of Q has a Hamiltonian path, since the existence of a Hamiltonian path implies the subgraph has a center.
		Assume H⊆ Q has a Hamiltonian path.
		Let w be a center and w_p, w_s be its predecessor and successor in the Hamiltonian path.
		It is clear that the subpath from the start of the Hamiltonian path to w_p remains a path in H\{w}; this is also true for the subpath from w_s to the end.
		Therefore if H\{w} is disconnected, there are two components and both have Hamiltonian paths.

			Otherwise suppose H\{w} is connected.
		Note that if P={v_1,…, v_p} is the prevailing path generated by Algorithm <ref>, C_F(v_j)∩ C_F(v_j+2) = ∅ or else v_j+2 would be forgotten later than v_j+1 and would have been chosen to be v_j+1 instead.
		Thus, there is some 1≤ℓ≤ q≤ p such that H\{w}⊆ C_F(v_ℓ)∪ C_F(v_ℓ+1)∪…∪ C_F(v_q) and since H\{w} is connected, for each ℓ≤ j< q the intersection of cliques C_F(v_j) and C_F(v_j+1) is non-empty.
		Consequently, the ordering of the vertices in the Hamiltonian path of Q must also define a Hamiltonian path of H\{w}.
	
	Since any linear coloring ψ of the prevailing subgraph Q must also be a centered coloring, (Q)≤ |ψ|.
	To get a bound on the treedepth of G, we focus on the relationship between Q and G\ Q.
	In particular, we show that the components of G\ Q use fewer than |ψ| colors by proving that each such component has an apex in the prevailing path.
	
		Let P,Q be a prevailing path and subgraph of an interval graph G.
		For each component X of G\ Q, there is a vertex a∈ P such that X⊆ N(a).
	
	
		For 1≤ j ≤ p, let 𝒳_j be the set of components of G[⋃_i = F(v_j-1)+1^F(v_j)-1 C_i]\ Q, defining F(v_0) = 0.
		By this definition and the fact that v_j is a member of both C_F(v_j-1) and C_F(v_j),  v_j is a neighbor of all vertices in X for each X∈𝒳_j.
		Thus it suffices to show that ⋃_j=1^p𝒳_j are the components of G\ Q.

			Since V(Q) = ⋃_j=1^p C_F(v_j), V(G) = V(Q) ∪ V(𝒳_1) ∪…∪ V(𝒳_p) and V(Q)∩⋃_j=1^p𝒳_j = ∅.
		Hence, if X∈𝒳_j is not a component of G\ Q, then there must be some component X'∈𝒳_i for which i≠ j and there exists u∈ X and u'∈ X' and uu'∈ E(G).
		But C_F(v_j)∪ C_F(v_j+1) has no common vertices with X and separates it from any vertices in 𝒳_i.
		An analogous statement for X' is true as well, so no such edges uu' exist.
		Therefore we conclude that ⋃_1≤ j≤ p𝒳_j are the components of G\ Q and the lemma is proven.
	

	We can now establish a polynomial upper bound on the treedepth of interval graphs, proving Theorem <ref>.
	
	
		Let 𝒜 be the algorithm that constructs a treedepth decomposition 𝒯 of G by finding a prevailing subgraph Q (Algorithm <ref>), using ψ|_Q to create a treedepth decomposition of Q, and recursively constructing treedepth decompositions of G\ Q.
		If depth(𝒯) ≤ k^2 and 𝒜 runs in polynomial time, then the canonical centered coloring of 𝒯 is a centered coloring of G of size at most k^2.
		We prove 𝒜 satisfies these requirements by induction on k = |ψ|.
		At k = 1, the graph consists of isolated vertices and 𝒜 trivially constructs a treedepth decomposition of G of depth 1 in polynomial time.

		Assume 𝒜 has the desired properties for linear colorings of size at most k-1.
		Because the maximal cliques of an interval graph can be enumerated and ordered in polynomial time (Proposition <ref>), identifying Q via Algorithm <ref> can be done in polynomial time.
		By Lemma <ref>, the canonical treedepth decomposition of Q has depth at most k.
		Since every component X of G\ Q has an apex a in P (Lemma <ref>), we can assume a is an ancestor in 𝒯 of each vertex in X (Lemma <ref>).
		Because ψ is proper, ψ(a) does not appear in ψ|_X and since induced subgraphs of interval graphs are themselves interval graphs, 𝒜 finds a treedepth decomposition of X whose depth is at most (k-1)^2.
		Thus 𝒯 has depth k+(k-1)^2≤ k^2.
		The recursion only lasts k≤ n steps, so 𝒜 runs in polynomial time.
	

	

§ HARDNESS OF RECOGNIZING LINEAR COLORINGS

Based on the similarity in definition between linear and centered colorings, one might assume that computing them should be roughly equally difficult.
Finding a centered coloring of a fixed size is NP-hard <cit.>, but given a coloring of a graph, we can recognize whether it is centered in polynomial time by attempting to create the canonical treedepth decomposition; this procedure will identify a non-centered subgraph if the coloring is not centered.
To the contrary, we will prove that Linear Coloring Recognition, the problem of recognizing whether a coloring is linear, is co-NP-complete.
In order to prove the hardness of Linear Coloring Recognition, we first define a dual problem.
The Non-centered Path problem takes a graph G and coloring ψ as input and decides whether G has a non-centered path P.
We focus on proving the hardness of Non-centered Path because a certificate to that problem is easily definable:  a path where every color appears at least twice.




	Non-centered Path is NP-complete.


	A certificate to Non-centered Path can be verified in linear time by iterating over all vertices in the path and counting color occurrences.
	Thus, Non-centered Path is in NP.

		We prove NP-hardness by reducing from CNF-SAT.
	Given a CNF-SAT formula Φ with variables x_1,… x_n and clauses C_1,… C_m, we construct a graph G and coloring ψ that will have a non-centered path if and only if Φ is satisfiable.
	We assume that Φ satisfies the following properties:
	
		
  * Every variable appears at most once in each clause.
		
  * No clause contains both a variable and its negation.
		
  * Every variable appears as a positive literal and negative literal.
	
	We can assume (1) since the disjunction operation is idempotent.
	Every clause for which (2) does not hold is satisfied by any truth assignment of the variables and thus can be removed without changing the satisfiability of Φ.
	If variable x_i appears only positively then assigning x_i to be false does not cause any clauses to be satisfied.
	Therefore, it is sufficient to set x_i to true and only consider the clauses of Φ that do not contain x_i; since the analogous statement is true when x_i does not appear positively, we can assume (3).

		The variables of Φ are represented by a set of vertices U = {u_0,…, u_n}.
	For each x_i, we connect u_i-1 and u_i with two paths P^T_i and P^F_i; we will force the non-centered path to contain vertices from exactly one of P^T_i and P^F_i, which will correspond to whether x_i was set to true or false.
	The path P^T_i contains one vertex for each C_j in which x_i appears positively while P^F_i contains one vertex for each C_j in which the negation of x_i appears.
	By assumption (2), we can uniquely label the vertex on P^T_i∪ P^F_i corresponding to clause C_j as w_i,j and the order of the vertices on P^T_i and P^F_i can be chosen arbitrarily.
	To complete the construction of G, we add path P_0 = u'_1, u'_2, …, u'_n, w'_1, w'_2, …, w'_m such that w'_m is adjacent to u_0 and all other vertices on P_0 have no additional edges.
	Finally, we attach a pendant vertex u'_0 to u_n.
	Since each vertex w_i,j corresponds to a unique literal in Φ and |U| + |P_0| = 2n+m+1, G has size linear in the size of Φ.

		To encode satisfaction of clauses, we color G with coloring ψ: V(G)→{0,…, n+m} such that ψ(u_i) = ψ(u'_i) = i and ψ(w'_j) = ψ(w_i,j) = n+j.
	In this way, we force any non-centered path to contain all colors and color j+n appears twice if and only if C_j is satisfied.
	An example can be found in Figure <ref>.

		We now prove that Φ is satisfiable iff G contains a path Q with no center.
	Given a satisfying assignment of Φ, let P^*_i be P^T_i if x_i is set to true and P^F_i if x_i is set to false.
	Then Q = P_0· u_0 · P^*_1· u_1 ·…· P^*_n · u_n · u'_0, is a non-centered path since it contains all pairs u_i, u'_i and ⋃_1≤ i≤ n P^*_i contains a vertex with the same color as each vertex in ⋃_1≤ j≤ m w'_j.

		To prove the reverse direction suppose G contains a non-centered path Q.
	Let U' = {u'_0,…, u'_n}.
	Since each vertex in U' shares a color with exactly one other vertex and that vertex is a member of U, Q contains a vertex from U iff Q contains a vertex from U'.
	By our construction of P_0 and assumptions about Φ, no component of G\ (U∪ U') contains two vertices of the same color.
	Thus, Q must contain vertices from U, U', and G\ (U∪ U').
	For any 0≤ i≠ j≤ n, every u_ju'_j path contains u_i or u'_i, which implies that (U∪ U')⊂ Q and Q is a u'_1u'_0 path.
	In order for Q to be connected, P_0⊆ Q and in order for it to be a path, exactly one of P^T_i and P^F_i (denote it P^*_i) is a subpath of Q for each 1≤ i≤ n.
	Since the colors in w'_1,… w'_m are unique, ⋃_1≤ i≤ n P^*_i contains at least one vertex of each color on [n+1, n+m], which corresponds to a selection of truth assignments to the variables of Φ such that every clause is satisfied.



	Linear Coloring Recognition is co-NP-complete.


The co-NP-hardness of recognizing linear colorings is compounded by three stronger hardness implications.
First, the coloring ψ given in Theorem <ref> has size m+n+1, which means that unless the exponential time hypothesis <cit.> fails, there is no 2^o(k) algorithm to recognize a linear coloring of size k.
Second, the graph G constructed in the proof of Theorem <ref> is outerplanar with pathwidth two, which implies that neither treewidth-style dynamic programming nor a Baker-style layering approach is likely to solve this problem efficiently.
Finally, by subdividing each edge and coloring all subdivision vertices with a (single) new color, we obtain a bipartite graph with degeneracy two, proving hardness for each of those classes.
Nonetheless, the fact that (G) = O(log m + log n) while |ψ| = m+n+1 leaves open the possibility that Linear Coloring Recognition becomes easier for colorings of minimum size.

	

§ CONCLUSION

We have introduced p-linear and linear colorings as an alternative to p-centered and centered colorings for use in algorithms for classes of bounded expansion.
The p-linear colorings are computable in polynomial time and require a constant number of colors in classes of bounded expansion, while inducing graphs of bounded treedepth for all small sets of colors, allowing direct substitution in existing algorithmic pipelines.
A major direction for future work is to bring the upper bound on (k) of poly(k) closer to the lower bound of 2k.
In particular, it appears our current toolkit for analyzing linear colorings must be expanded in order to prove (or disprove) Conjecture <ref>.
We also believe it is worth studying whether recognizing linear colorings can be done in polynomial time if we assume the coloring is of size (G).
Finally, using p-linear colorings in practice will require an efficient method for translating a linear coloring into a treedepth decomposition.
Although there exist general-purpose algorithms to find treedepth decompositions efficiently in graphs of bounded linear coloring number (e.g. <cit.>), a more specialized algorithm that avoids “heavy machinery” is likely necessary to be practically useful.



§ ACKNOWLEDGMENTS

r0.17

    < g r a p h i c s >



    < g r a p h i c s >


The authors would like to thank Felix Reidl and Fernando Sánchez-Villaamil for bringing these colorings to our attention and several anonymous reviewers for their helpful suggestion.
This work was supported in part by the DARPA GRAPHS Program and the Gordon & Betty Moore Foundation's Data-Driven Discovery Initiative through Grants SPAWARN66001-14-1-4063 and GBMF4560 to Blair D. Sullivan.
The research of Marcin Pilipczuk is a part of a project that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme, grant agreement No 714704.

	spmpsci
	
	
