Variants of vertex and edge colorings of graphs/ Drimit Pattanayak

Thesis (Ph.D.)- Indian statistical Institute, 2024

Includes conclusion

Linear arboricity of 3-degenerate and 2-degenerate graphs -- Optimal linear coloring of 3-degenerate graphs -- Linear time algorithms -- p-centered colorings of grids

Guided by Prof. Mathew C. Francis

A k-linear coloring of a graph G is an edge coloring of G with k colors so that each
color class forms a linear forest—a forest whose each connected component is a path.
The linear arboricity χ
′
l
(G) of G is the minimum integer k such that there exists a
k-linear coloring of G. Akiyama, Exoo and Harary conjectured in 1980 that for every
graph G, χ
′
l
(G) ≤
l
∆(G)+1
2
m
where ∆(G) is the maximum degree of G. First, we prove
the conjecture for 3-degenerate graphs. This establishes the conjecture for graphs of
treewidth at most 3 and provides an alternative proof for the conjecture in some classes
of graphs like cubic graphs and triangle-free planar graphs for which the conjecture
was already known to be true. Next, we prove that for every 2-degenerate graph G,
χ
′
l
(G) = l
∆(G)
2
m
if ∆(G) ≥ 5. We conjecture that this equality holds also when ∆(G) ∈
{3, 4} and show that this is the case for some well-known subclasses of 2-degenerate
graphs. All the above proofs can be converted into linear time algorithms that produce
linear colorings of input 3-degenerate and 2-degenerate graphs using a number of colors
matching the upper bounds on linear arboricity proven for these classes of graphs.
Motivated by this, we then show that for every 3-degenerate graph, χ
′
l
(G) = l
∆(G)
2
m
if ∆(G) ≥ 9. Further, we show that this line of reasoning can be extended to obtain
a different proof for the linear arboricity conjecture for all 3-degenerate graphs. This
proof has the advantage that it gives rise to a simpler linear time algorithm for obtaining
a linear coloring of an input 3-degenerate graph G using at most one more color than
the linear arboricity of G.
A p-centered coloring of a graph G, where p is a positive integer, is a coloring of the
vertices of G in such a way that every connected subgraph of G either contains a vertex
with a unique color or contains more than p different colors. As p increases, we get a
hierarchy of more and more restricted colorings, starting from proper vertex colorings,
which are exactly the 1-centered colorings. Debski, Felsner, Micek and Schroder proved that bounded degree graphs have p-centered colorings using O(p) colors. But since their
method is based on the technique of entropy compression, it cannot be used to obtain
a description of an explicit coloring even for relatively simple graphs. In fact, they ask if an explicit p-centered coloring using O(p) colors can be constructed for the planar grid. We answer their question by demonstrating a construction for obtaining such a coloring for the planar grid.