Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDefective and Clustered Choosability of Sparse Graphs
69
0
0.0
(
0
)
Added by
David Wood
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
An (improper) graph colouring has defect $d$ if each monochromatic subgraph has maximum degree at most $d$, and has clustering $c$ if each monochromatic component has at most $c$ vertices. This paper studies defective and clustered list-colourings for graphs with given maximum average degree. We prove that every graph with maximum average degree less than $frac{2d+2}{d+2} k$ is $k$-choosable with defect $d$. This improves upon a similar result by Havet and Sereni [J. Graph Theory, 2006]. For clustered choosability of graphs with maximum average degree $m$, no $(1-epsilon)m$ bound on the number of colours was previously known. The above result with $d=1$ solves this problem. It implies that every graph with maximum average degree $m$ is $lfloor{frac{3}{4}m+1}rfloor$-choosable with clustering 2. This extends a result of Kopreski and Yu [Discrete Math., 2017] to the setting of choosability. We then prove two results about clustered choosability that explore the trade-off between the number of colours and the clustering. In particular, we prove that every graph with maximum average degree $m$ is $lfloor{frac{7}{10}m+1}rfloor$-choosable with clustering $9$, and is $lfloor{frac{2}{3}m+1}rfloor$-choosable with clustering $O(m)$. As an example, the later result implies that every biplanar graph is 8-choosable with bounded clustering. This is the best known result for the clustered version of the earth-moon problem. The results extend to the setting where we only consider the maximum average degree of subgraphs with at least some number of vertices. Several applications are presented.
rate research
Read More
Assume $ k $ is a positive integer, $ lambda={k_1,k_2,...,k_q} $ is a partition of $ k $ and $ G $ is a graph. A $lambda$-assignment of $ G $ is a $ k $-assignment $ L $ of $ G $ such that the colour set $ bigcup_{vin V(G)} L(v) $ can be partitioned into $ q $ subsets $ C_1cup C_2cupcdotscup C_q $ and for each vertex $ v $ of $ G $, $ |L(v)cap C_i|=k_i $. We say $ G $ is $lambda$-choosable if for each $lambda$-assignment $ L $ of $ G $, $ G $ is $ L $-colourable. In particular, if $ lambda={k} $, then $lambda$-choosable is the same as $ k $-choosable, if $ lambda={1, 1,...,1} $, then $lambda$-choosable is equivalent to $ k $-colourable. For the other partitions of $ k $ sandwiched between $ {k} $ and $ {1, 1,...,1} $ in terms of refinements, $lambda$-choosability reveals a complex hierarchy of colourability of graphs. Assume $lambda={k_1, ldots, k_q} $ is a partition of $ k $ and $lambda $ is a partition of $ kge k $. We write $ lambdale lambda $ if there is a partition $lambda={k_1, ldots, k_q}$ of $k$ with $k_i ge k_i$ for $i=1,2,ldots, q$ and $lambda$ is a refinement of $lambda$. It follows from the definition that if $ lambdale lambda $, then every $lambda$-choosable graph is $lambda$-choosable. It was proved in [X. Zhu, A refinement of choosability of graphs, J. Combin. Theory, Ser. B 141 (2020) 143 - 164] that the converse is also true. This paper strengthens this result and proves that for any $ lambda otle lambda $, for any integer $g$, there exists a graph of girth at least $g$ which is $lambda$-choosable but not $lambda$-choosable.
A star $k$-coloring is a proper $k$-coloring where the union of two color classes induces a star forest. While every planar graph is 4-colorable, not every planar graph is star 4-colorable. One method to produce a star 4-coloring is to partition the vertex set into a 2-independent set and a forest; such a partition is called an I,F-partition. We use a combination of potential functions and discharging to prove that every graph with maximum average degree less than $frac{5}{2}$ has an I,F-partition, which is sharp and answers a question of Cranston and West [A guide to the discharging method, arXiv:1306.4434]. This result implies that planar graphs of girth at least 10 are star 4-colorable, improving upon previous results of Bu, Cranston, Montassier, Raspaud, and Wang [Star coloring of sparse graphs, J. Graph Theory 62 (2009), 201-219].
All planar graphs are 4-colorable and 5-choosable, while some planar graphs are not 4-choosable. Determining which properties guarantee that a planar graph can be colored using lists of size four has received significant attention. In terms of constraining the structure of the graph, for any $ell in {3,4,5,6,7}$, a planar graph is 4-choosable if it is $ell$-cycle-free. In terms of constraining the list assignment, one refinement of $k$-choosability is choosability with separation. A graph is $(k,s)$-choosable if the graph is colorable from lists of size $k$ where adjacent vertices have at most $s$ common colors in their lists. Every planar graph is $(4,1)$-choosable, but there exist planar graphs that are not $(4,3)$-choosable. It is an open question whether planar graphs are always $(4,2)$-choosable. A chorded $ell$-cycle is an $ell$-cycle with one additional edge. We demonstrate for each $ell in {5,6,7}$ that a planar graph is $(4,2)$-choosable if it does not contain chorded $ell$-cycles.
A (not necessarily proper) vertex colouring of a graph has clustering $c$ if every monochromatic component has at most $c$ vertices. We prove that planar graphs with maximum degree $Delta$ are 3-colourable with clustering $O(Delta^2)$. The previous best bound was $O(Delta^{37})$. This result for planar graphs generalises to graphs that can be drawn on a surface of bounded Euler genus with a bounded number of crossings per edge. We then prove that graphs with maximum degree $Delta$ that exclude a fixed minor are 3-colourable with clustering $O(Delta^5)$. The best previous bound for this result was exponential in $Delta$.
Graham and Pollak showed that the vertices of any graph $G$ can be addressed with $N$-tuples of three symbols, such that the distance between any two vertices may be easily determined from their addresses. An addressing is optimal if its length $N$ is minimum possible. In this paper, we determine an addressing of length $k(n-k)$ for the Johnson graphs $J(n,k)$ and we show that our addressing is optimal when $k=1$ or when $k=2, n=4,5,6$, but not when $n=6$ and $k=3$. We study the addressing problem as well as a variation of it in which the alphabet used has more than three symbols, for other graphs such as complete multipartite graphs and odd cycles. We also present computations describing the distribution of the minimum length of addressings for connected graphs with up to $10$ vertices. Motivated by these computations we settle a problem of Graham, showing that most graphs on $n$ vertices have an addressing of length at most $n-(2-o(1))log_2 n$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
