Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn list 3-dynamic coloring of near-triangulations
96
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
An $r$-dynamic $k$-coloring of a graph $G$ is a proper $k$-coloring such that for any vertex $v$, there are at least $min{r, deg_G(v) }$ distinct colors in $N_G(v)$. The $r$-dynamic chromatic number $chi_r^d(G)$ of a graph $G$ is the least $k$ such that there exists an $r$-dynamic $k$-coloring of $G$. The list $r$-dynamic chromatic number of a graph $G$ is denoted by $ch_r^d(G)$. Loeb et al. $[11]$ showed that $ch_3^d(G)leq 10$ for every planar graph $G$, and there is a planar graph $G$ with $chi_3^d(G)= 7$. In this paper, we study a special class of planar graphs which have better upper bounds of $ch_3^d(G)$. We prove that $ch_3^d(G) leq 6$ if $G$ is a planar graph which is near-triangulation, where a near-triangulation is a planar graph whose bounded faces are all 3-cycles.
rate research
Read More
Motivated by the ErdH{o}s-Faber-Lovasz (EFL) conjecture for hypergraphs, we consider the list edge coloring of linear hypergraphs. We discuss several conjectures for list edge coloring linear hypergraphs that generalize both EFL and Vizings theorem for graphs. For example, we conjecture that in a linear hypergraph of rank 3, the list edge chromatic number is at most 2 times the maximum degree plus 1. We show that for sufficiently large fixed rank and sufficiently large degree, the conjectures are true.
A strong edge-coloring of a graph $G$ is an edge-coloring such that any two edges on a path of length three receive distinct colors. We denote the strong chromatic index by $chi_{s}(G)$ which is the minimum number of colors that allow a strong edge-coloring of $G$. ErdH{o}s and Nev{s}etv{r}il conjectured in 1985 that the upper bound of $chi_{s}(G)$ is $frac{5}{4}Delta^{2}$ when $Delta$ is even and $frac{1}{4}(5Delta^{2}-2Delta +1)$ when $Delta$ is odd, where $Delta$ is the maximum degree of $G$. The conjecture is proved right when $Deltaleq3$. The best known upper bound for $Delta=4$ is 22 due to Cranston previously. In this paper we extend the result of Cranston to list strong edge-coloring, that is to say, we prove that when $Delta=4$ the upper bound of list strong chromatic index is 22.
The textit{$k$-weak-dynamic number} of a graph $G$ is the smallest number of colors we need to color the vertices of $G$ in such a way that each vertex $v$ of degree $d(v)$ sees at least $rm{min}{k,d(v)}$ colors on its neighborhood. We use reducible configurations and list coloring of graphs to prove that all planar graphs have 3-weak-dynamic number at most 6.
Golovach, Paulusma and Song (Inf. Comput. 2014) asked to determine the parameterized complexity of the following problems parameterized by $k$: (1) Given a graph $G$, a clique modulator $D$ (a clique modulator is a set of vertices, whose removal results in a clique) of size $k$ for $G$, and a list $L(v)$ of colors for every $vin V(G)$, decide whether $G$ has a proper list coloring; (2) Given a graph $G$, a clique modulator $D$ of size $k$ for $G$, and a pre-coloring $lambda_P: X rightarrow Q$ for $X subseteq V(G),$ decide whether $lambda_P$ can be extended to a proper coloring of $G$ using only colors from $Q.$ For Problem 1 we design an $O^*(2^k)$-time randomized algorithm and for Problem 2 we obtain a kernel with at most $3k$ vertices. Banik et al. (IWOCA 2019) proved the the following problem is fixed-parameter tractable and asked whether it admits a polynomial kernel: Given a graph $G$, an integer $k$, and a list $L(v)$ of exactly $n-k$ colors for every $v in V(G),$ decide whether there is a proper list coloring for $G.$ We obtain a kernel with $O(k^2)$ vertices and colors and a compression to a variation of the problem with $O(k)$ vertices and $O(k^2)$ colors.
A graph $G$ is called $3$-choice critical if $G$ is not $2$-choosable but any proper subgraph is $2$-choosable. A characterization of $3$-choice critical graphs was given by Voigt in [On list Colourings and Choosability of Graphs, Habilitationsschrift, Tu Ilmenau(1998)]. Voigt conjectured that if $G$ is a bipartite $3$-choice critical graph, then $G$ is $(4m, 2m)$-choosable for every integer $m$. This conjecture was disproved by Meng, Puleo and Zhu in [On (4, 2)-Choosable Graphs, Journal of Graph Theory 85(2):412-428(2017)]. They showed that if $G=Theta_{r,s,t}$ where $r,s,t$ have the same parity and $min{r,s,t} ge 3$, or $G=Theta_{2,2,2,2p}$ with $p ge 2$, then $G$ is bipartite $3$-choice critical, but not $(4,2)$-choosable. On the other hand, all the other bipartite 3-choice critical graphs are $(4,2)$-choosable. This paper strengthens the result of Meng, Puleo and Zhu and shows that all the other bipartite $3$-choice critical graphs are $(4m,2m)$-choosable for every integer $m$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
