2025 : 9 : 29

Somayeh Moradi

Academic rank: Associate Professor
ORCID:
Education: PhD.
ScopusId:
HIndex:
Faculty: Basic Science
Address:
Phone:

Research

Title
An algebraic criterion for the choosability of graphs
Type
JournalPaper
Keywords
Choosability, list coloring
Year
2015
Journal GRAPHS AND COMBINATORICS
DOI
Researchers Saieed Akbari ، Dariush Kiani ، Fatemeh Mohammadi ، Somayeh Moradi ، Farhad Rahmati

Abstract

Let $G$ be a graph of order $n$ and size $m$. Suppose that $f:V(G)\rightarrow \mathbb{N}$ is a function such that $\sum_{v\in V(G)}f(v)=m+n$. In this paper we provide a criterion for $f$-choosability of $G$. Using this criterion, it is shown that the choice number of the complete $k$-partite graph $K_{2,2,\ldots,2}$ is $k$, which is a well-known result due to Erd{\"o}s, Rubin and Taylor. Among other results we study the $f$-choosability of the complete $k$-partite graphs with part sizes at most $2$, when $f(v)\in \{k-1,k\}$, for every vertex $v\in V(G)$.