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 |