Online Public Access Catalogue (OPAC)
Library,Documentation and Information Science Division

“A research journal serves that narrow

borderland which separates the known from the unknown”

-P.C.Mahalanobis


Variants of vertex and edge colorings of graphs/ (Record no. 436532)

MARC details
000 -LEADER
fixed length control field 03647nam a22002537a 4500
003 - CONTROL NUMBER IDENTIFIER
control field ISI Library, Kolkata
005 - DATE AND TIME OF LATEST TRANSACTION
control field 20240930143854.0
008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION
fixed length control field 240930b |||||||| |||| 00| 0 eng d
040 ## - CATALOGING SOURCE
Original cataloging agency ISI Library
Language of cataloging English
082 04 - DEWEY DECIMAL CLASSIFICATION NUMBER
Edition number 23
Classification number 511.56
Item number D779
100 1# - MAIN ENTRY--PERSONAL NAME
Personal name Pattanayak, Drimit
Relator term author
245 ## - TITLE STATEMENT
Title Variants of vertex and edge colorings of graphs/
Statement of responsibility, etc Drimit Pattanayak
260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT)
Place of publication, distribution, etc Kolkata:
Name of publisher, distributor, etc Indian Statistical Institute,
Date of publication, distribution, etc 2024
300 ## - PHYSICAL DESCRIPTION
Extent 111 pages;
502 ## - DISSERTATION NOTE
Dissertation note Thesis (Ph.D.)- Indian statistical Institute, 2024
504 ## - BIBLIOGRAPHY, ETC. NOTE
Bibliography, etc Includes conclusion
505 0# - FORMATTED CONTENTS NOTE
Formatted contents note Linear arboricity of 3-degenerate and 2-degenerate graphs -- Optimal linear coloring of 3-degenerate graphs -- Linear time algorithms -- p-centered colorings of grids
508 ## - CREATION/PRODUCTION CREDITS NOTE
Creation/production credits note Guided by Prof. Mathew C. Francis
520 ## - SUMMARY, ETC.
Summary, etc A k-linear coloring of a graph G is an edge coloring of G with k colors so that each<br/>color class forms a linear forest—a forest whose each connected component is a path.<br/>The linear arboricity χ<br/>′<br/>l<br/>(G) of G is the minimum integer k such that there exists a<br/>k-linear coloring of G. Akiyama, Exoo and Harary conjectured in 1980 that for every<br/>graph G, χ<br/>′<br/>l<br/>(G) ≤<br/>l<br/>∆(G)+1<br/>2<br/>m<br/>where ∆(G) is the maximum degree of G. First, we prove<br/>the conjecture for 3-degenerate graphs. This establishes the conjecture for graphs of<br/>treewidth at most 3 and provides an alternative proof for the conjecture in some classes<br/>of graphs like cubic graphs and triangle-free planar graphs for which the conjecture<br/>was already known to be true. Next, we prove that for every 2-degenerate graph G,<br/>χ<br/>′<br/>l<br/>(G) = l<br/>∆(G)<br/>2<br/>m<br/>if ∆(G) ≥ 5. We conjecture that this equality holds also when ∆(G) ∈<br/>{3, 4} and show that this is the case for some well-known subclasses of 2-degenerate<br/>graphs. All the above proofs can be converted into linear time algorithms that produce<br/>linear colorings of input 3-degenerate and 2-degenerate graphs using a number of colors<br/>matching the upper bounds on linear arboricity proven for these classes of graphs.<br/>Motivated by this, we then show that for every 3-degenerate graph, χ<br/>′<br/>l<br/>(G) = l<br/>∆(G)<br/>2<br/>m<br/>if ∆(G) ≥ 9. Further, we show that this line of reasoning can be extended to obtain<br/>a different proof for the linear arboricity conjecture for all 3-degenerate graphs. This<br/>proof has the advantage that it gives rise to a simpler linear time algorithm for obtaining<br/>a linear coloring of an input 3-degenerate graph G using at most one more color than<br/>the linear arboricity of G.<br/>A p-centered coloring of a graph G, where p is a positive integer, is a coloring of the<br/>vertices of G in such a way that every connected subgraph of G either contains a vertex<br/>with a unique color or contains more than p different colors. As p increases, we get a<br/>hierarchy of more and more restricted colorings, starting from proper vertex colorings,<br/>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<br/>method is based on the technique of entropy compression, it cannot be used to obtain<br/>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.
650 #4 - SUBJECT ADDED ENTRY--TOPICAL TERM
Topical term or geographic name as entry element Graph theory
650 #4 - SUBJECT ADDED ENTRY--TOPICAL TERM
Topical term or geographic name as entry element Coloring of graphs
856 ## - ELECTRONIC LOCATION AND ACCESS
Uniform Resource Identifier <a href="http://dspace.isical.ac.in:8080/jspui/handle/10263/7465">http://dspace.isical.ac.in:8080/jspui/handle/10263/7465</a>
Link text Full Text
942 ## - ADDED ENTRY ELEMENTS (KOHA)
Source of classification or shelving scheme Dewey Decimal Classification
Koha item type THESIS
Holdings
Lost status Not for loan Home library Current library Date acquired Full call number Accession Number Koha item type Public note
    ISI Library, Kolkata ISI Library, Kolkata 30/09/2024 511.56 D779 TH596 THESIS E-Thesis
Library, Documentation and Information Science Division, Indian Statistical Institute, 203 B T Road, Kolkata 700108, INDIA
Phone no. 91-33-2575 2100, Fax no. 91-33-2578 1412, ksatpathy@isical.ac.in