Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDistance-Two Colorings of Barnette Graphs
90
0
0.0
(
0
)
Added by
Pavol Hell
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Barnette identified two interesting classes of cubic polyhedral graphs for which he conjectured the existence of a Hamiltonian cycle. Goodey proved the conjecture for the intersection of the two classes. We examine these classes from the point of view of distance-two colorings. A distance-two $r$-coloring of a graph $G$ is an assignment of $r$ colors to the vertices of $G$ so that any two vertices at distance at most two have different colors. Note that a cubic graph needs at least four colors. The distance-two four-coloring problem for cubic planar graphs is known to be NP-complete. We claim the problem remains NP-complete for tri-connected bipartite cubic planar graphs, which we call type-one Barnette graphs, since they are the first class identified by Barnette. By contrast, we claim the problem is polynomial for cubic plane graphs with face sizes $3, 4, 5,$ or $6$, which we call type-two Barnette graphs, because of their relation to Barnettes second conjecture. We call Goodey graphs those type-two Barnette graphs all of whose faces have size $4$ or $6$. We fully describe all Goodey graphs that admit a distance-two four-coloring, and characterize the remaining type-two Barnette graphs that admit a distance-two four-coloring according to their face size. For quartic plane graphs, the analogue of type-two Barnette graphs are graphs with face sizes $3$ or $4$. For this class, the distance-two four-coloring problem is also polynomial; in fact, we can again fully describe all colorable instances -- there are exactly two such graphs.
rate research
Read More
$H_q(n,d)$ is defined as the graph with vertex set ${mathbb Z}_q^n$ and where two vertices are adjacent if their Hamming distance is at least $d$. The chromatic number of these graphs is presented for various sets of parameters $(q,n,d)$. For the $4$-colorings of the graphs $H_2(n,n-1)$ a notion of robustness is introduced. It is based on the tolerance of swapping colors along an edge without destroying properness of the coloring. An explicit description of the maximally robust $4$-colorings of $H_2(n,n-1)$ is presented.
A graph drawn in the plane with n vertices is k-fan-crossing free for k > 1 if there are no k+1 edges $g,e_1,...e_k$, such that $e_1,e_2,...e_k$ have a common endpoint and $g$ crosses all $e_i$. We prove a tight bound of 4n-8 on the maximum number of edges of a 2-fan-crossing free graph, and a tight 4n-9 bound for a straight-edge drawing. For k > 2, we prove an upper bound of 3(k-1)(n-2) edges. We also discuss generalizations to monotone graph properties.
A proper edge-coloring of a graph $G$ with colors $1,ldots,t$ is called an emph{interval cyclic $t$-coloring} if all colors are used, and the edges incident to each vertex $vin V(G)$ are colored by $d_{G}(v)$ consecutive colors modulo $t$, where $d_{G}(v)$ is the degree of a vertex $v$ in $G$. A graph $G$ is emph{interval cyclically colorable} if it has an interval cyclic $t$-coloring for some positive integer $t$. The set of all interval cyclically colorable graphs is denoted by $mathfrak{N}_{c}$. For a graph $Gin mathfrak{N}_{c}$, the least and the greatest values of $t$ for which it has an interval cyclic $t$-coloring are denoted by $w_{c}(G)$ and $W_{c}(G)$, respectively. In this paper we investigate some properties of interval cyclic colorings. In particular, we prove that if $G$ is a triangle-free graph with at least two vertices and $Gin mathfrak{N}_{c}$, then $W_{c}(G)leq vert V(G)vert +Delta(G)-2$. We also obtain bounds on $w_{c}(G)$ and $W_{c}(G)$ for various classes of graphs. Finally, we give some methods for constructing of interval cyclically non-colorable graphs.
An edge-coloring of a graph $G$ with consecutive integers $c_{1},ldots,c_{t}$ is called an emph{interval $t$-coloring} if all colors are used, and the colors of edges incident to any vertex of $G$ are distinct and form an interval of integers. A graph $G$ is interval colorable if it has an interval $t$-coloring for some positive integer $t$. The set of all interval colorable graphs is denoted by $mathfrak{N}$. In 2004, Giaro and Kubale showed that if $G,Hin mathfrak{N}$, then the Cartesian product of these graphs belongs to $mathfrak{N}$. In the same year they formulated a similar problem for the composition of graphs as an open problem. Later, in 2009, the first author showed that if $G,Hin mathfrak{N}$ and $H$ is a regular graph, then $G[H]in mathfrak{N}$. In this paper, we prove that if $Gin mathfrak{N}$ and $H$ has an interval coloring of a special type, then $G[H]in mathfrak{N}$. Moreover, we show that all regular graphs, complete bipartite graphs and trees have such a special interval coloring. In particular, this implies that if $Gin mathfrak{N}$ and $T$ is a tree, then $G[T]in mathfrak{N}$.
We show that any proper coloring of a Kneser graph $KG_{n,k}$ with $n-2k+2$ colors contains a trivial color (i.e., a color consisting of sets that all contain a fixed element), provided $n>(2+epsilon)k^2$, where $epsilonto 0$ as $kto infty$. This bound is essentially tight.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
