All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

List Colorings with Distinct List Sizes, the Case of Complete Bipartite Graphs

The result's identifiers

  • Result code in IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10332568" target="_blank" >RIV/00216208:11320/16:10332568 - isvavai.cz</a>

  • Result on the web

    <a href="http://dx.doi.org/10.1002/jgt.21896" target="_blank" >http://dx.doi.org/10.1002/jgt.21896</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1002/jgt.21896" target="_blank" >10.1002/jgt.21896</a>

Alternative languages

  • Result language

    angličtina

  • Original language name

    List Colorings with Distinct List Sizes, the Case of Complete Bipartite Graphs

  • Original language description

    Let $f:V rightarrow mathbb{N}$ be a function on the vertex set of the graph $G=(V,E)$. The graph $G$ is {em $f$-choosable} if for every collection of lists with list sizes specified by $f$ there is a proper coloring using colors from the lists. The sum choice number, $chi_{sc}(G)$, is the minimum of $sum f(v)$, over all functions $f$ such that $G$ is $f$-choosable. It is known (Alon 1993, 2000) that if $G$ has average degree $d$, then the usual choice number $chi_ell(G)$ is at least $Omega(log d)$, so they grow simultaneously. In this paper we show that $chi_{sc}(G)/|V(G)|$ can be bounded while the minimum degree $delta_{min}(G)rightarrow infty$. Our main tool is to give tight estimates for the sum choice number of the unbalanced complete bipartite graph $K_{a,q}$.

  • Czech name

  • Czech description

Classification

  • Type

    J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

  • CEP classification

    BA - General mathematics

  • OECD FORD branch

Result continuities

  • Project

    <a href="/en/project/GPP201%2F12%2FP288" target="_blank" >GPP201/12/P288: Graph representations</a><br>

  • Continuities

    P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Others

  • Publication year

    2016

  • Confidentiality

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Data specific for result type

  • Name of the periodical

    Journal of Graph Theory

  • ISSN

    0364-9024

  • e-ISSN

  • Volume of the periodical

    82

  • Issue of the periodical within the volume

    2

  • Country of publishing house

    US - UNITED STATES

  • Number of pages

    10

  • Pages from-to

    218-227

  • UT code for WoS article

    000374341900006

  • EID of the result in the Scopus database

    2-s2.0-84940100316