NDLI: A Theorem about the Channel Assignment Problem

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Skrekovski, Riste Krl', Daniel
Copyright Year	2003
Abstract	A list channel assignment problem is a triple (G,L,w), where G is a graph, L is a function which assigns to each vertex of G a list of integers (colors), and w is a function which assigns to each edge of G a positive integer (its weight). A coloring c of the vertices of G is proper if c(v)\in L(v)$ for each vertex v and $\|c(u)-c(v)\|\ge w(uv)$ for each edge uv. A weighted degree $\deg_w(v)$ of a vertex v is the sum of the weights of the edges incident with v. If G is connected, $\|L(v)\|>\deg_w(v)$ for at least one v, and $\|L(v)\|\ge\deg_w(v)$ for all v, then a proper coloring always exists. A list channel assignment problem is balanced if $\|L(v)\|=\deg_w(v)$ for all v. We characterize all balanced list channel assignment problems (G,L,w) which admit a proper coloring. An application of this result is that each graph with maximum degree $\Delta\ge 2$ has an L(2,1)-labeling using integers $0,\ldots,\Delta^2+\Delta-1$.
Starting Page	426
Ending Page	437
Page Count	12
File Format	PDF
ISSN	08954801
DOI	10.1137/S0895480101399449
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	3
Volume Number	16
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-08-01
Access Restriction	Subscribed
Subject Keyword	graph coloring list-coloring Coloring of graphs and hypergraphs channel assignment problem
Content Type	Text
Resource Type	Article
Subject	Mathematics

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

A Brooks-Type Theorem for the Generalized List T-Coloring

The Channel Assignment Problem with Variable Weights

Real Number Channel Assignments for Lattices

Brooks-Type Theorems for Pair-List Colorings and List Homomorphisms

Optimal Real Number Graph Labellings of a Subfamily of Kneser Graphs

Labelings of Graphs with Fixed and Variable Edge-Weights

Graph Imperfection with a Co-Site Constraint

On List Coloring and List Homomorphism of Permutation and Interval Graphs

Griggs and Yeh's Conjecture and $L(p,1)$-labelings

A Theorem about the Channel Assignment Problem

Similar Documents

A Brooks-Type Theorem for the Generalized List T-Coloring

The Channel Assignment Problem with Variable Weights

Real Number Channel Assignments for Lattices

Brooks-Type Theorems for Pair-List Colorings and List Homomorphisms

Optimal Real Number Graph Labellings of a Subfamily of Kneser Graphs

Labelings of Graphs with Fixed and Variable Edge-Weights

Graph Imperfection with a Co-Site Constraint

On List Coloring and List Homomorphism of Permutation and Interval Graphs

Griggs and Yeh's Conjecture and $L(p,1)$-labelings

A Theorem about the Channel Assignment Problem