NDLI: $$(2+\epsilon )$$ -Nonrepetitive List Colouring of Paths

Content Provider	Springer Nature Link
Author	Zhao, Huanhua Zhu, Xuding
Copyright Year	2015
Abstract	A sequence $$a_1a_2\ldots a_p$$ is an r-repetition (for a real number $$r >1 $$ ) if $$p=\lceil rq \rceil $$ for some positive integer q, and $$a_j=a_{j+q}$$ for $$j=1,2,\ldots , p-q$$ . In other words, the sequence can be divided into $$\lceil r \rceil $$ blocks where all the blocks are the same, say, all the blocks equal to $$a_1a_2\ldots a_q$$ for some $$q \ge 1$$ , except that when r is not an integer, the last block is the prefix of $$a_1...a_q$$ of length $$ \lceil (r - \lfloor r \rfloor )q \rceil $$ . A colouring of the vertices of a graph G is r-nonrepetitive if there is no path in G for which the colour sequence of its vertices forms an r-repetition. The r-nonrepetitive chromatic number $$\pi _r(G)$$ of G is the minimum number of colours needed in an r-nonrepetitive colouring of G. A k-list assignment of a graph G is a mapping L which assigns a set L(v) of k permissible colours to each vertex v of G. The r-nonrepetitive choice number $$\pi _{rch}(G)$$ of G is the least integer k such that for every k-list assignment L, there is an r-nonrepetitive colouring c of G satisfying $$c(v)\in L(v)$$ for every vertex v of G. A classical result of Thue asserts that $$\pi _2(P_n)\le 3$$ for all n. It is known that $$ \pi _{2ch}(P_n) \le 4$$ for all n. However, it remains an open problem whether $$\pi _{2ch}(P_n) \le 3$$ for all n. This paper proves that for any $$\epsilon > 0$$ , $$\pi _{(2+\epsilon )ch}(P_n) \le 3$$ for all n.
Starting Page	1635
Ending Page	1640
Page Count	6
File Format	PDF
ISSN	09110119
Journal	Graphs and Combinatorics
Volume Number	32
Issue Number	4
e-ISSN	14355914
Language	English
Publisher	Springer Japan
Publisher Date	2015-11-30
Publisher Place	Tokyo
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Non-repetitive list colouring Entropy method Non-repetitive chromatic number Path Combinatorics Engineering Design
Content Type	Text
Resource Type	Article
Subject	Discrete Mathematics and Combinatorics Theoretical Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On the Facial Thue Choice Number of Plane Graphs Via Entropy Compression Method

List-Coloring Claw-Free Graphs with Small Clique Number

The Relaxed Game Chromatic Number of Graphs with Cut-Vertices

Acyclic, Star and Oriented Colourings of Graph Subdivisions

Nonrepetitive Colouring via Entropy Compression

On Three-Color Ramsey Number of Paths

Acyclic, Star and Oriented Colourings of Graph Subdivisions

Nonrepetitive colouring via entropy compression

Dominator Colorings of Certain Cartesian Products of Paths and Cycles

$$(2+\epsilon )$$ -Nonrepetitive List Colouring of Paths

Similar Documents

On the Facial Thue Choice Number of Plane Graphs Via Entropy Compression Method

List-Coloring Claw-Free Graphs with Small Clique Number

The Relaxed Game Chromatic Number of Graphs with Cut-Vertices

Acyclic, Star and Oriented Colourings of Graph Subdivisions

Nonrepetitive Colouring via Entropy Compression

On Three-Color Ramsey Number of Paths

Acyclic, Star and Oriented Colourings of Graph Subdivisions

Nonrepetitive colouring via entropy compression

Dominator Colorings of Certain Cartesian Products of Paths and Cycles

$$(2+\epsilon )$$ -Nonrepetitive List Colouring of Paths