oalib

Publish in OALib Journal

ISSN: 2333-9721

APC: Only $99

Submit

Any time

2019 ( 76 )

2018 ( 764 )

2017 ( 790 )

2016 ( 755 )

Custom range...

Search Results: 1 - 10 of 60989 matches for " Gexin Yu "
All listed articles are free for downloading (OA Articles)
Page 1 /60989
Display every page Item
Strong edge-colorings for k-degenerate graphs
Gexin Yu
Mathematics , 2012,
Abstract: We prove that the strong chromatic index for each $k$-degenerate graph with maximum degree $\Delta$ is at most $(4k-2)\Delta-k(2k-1)+1$.
New Bounds on the Minimum Density of a Vertex Identifying Code for the Infinite Hexagonal Grid
Ari Cukierman,Gexin Yu
Mathematics , 2011,
Abstract: For a graph, $G$, and a vertex $v \in V(G)$, let $N[v]$ be the set of vertices adjacent to and including $v$. A set $D \subseteq V(G)$ is a vertex identifying code if for any two distinct vertices $v_1, v_2 \in V(G)$, the vertex sets $N[v_1] \cap D$ and $N[v_2] \cap D$ are distinct and non-empty. We consider the minimum density of a vertex identifying code for the infinite hexagonal grid. In 2000, Cohen et al. constructed two codes with a density of $3/7 \approx 0.428571$, and this remains the best known upper bound. Until now, the best known lower bound was $12/29 \approx 0.413793$ and was proved by Cranston and Yu in 2009. We present three new codes with a density of 3/7, and we improve the lower bound to $5/12 \approx 0.416667$.
A relaxation of Steinberg's Conjecture
Owen Hill,Gexin Yu
Mathematics , 2012,
Abstract: A graph is $(c_1, c_2, ..., c_k)$-colorable if the vertex set can be partitioned into $k$ sets $V_1,V_2, ..., V_k$, such that for every $i: 1\leq i\leq k$ the subgraph $G[V_i]$ has maximum degree at most $c_i$. We show that every planar graph without 4- and 5-cycles is $(1, 1, 0)$-colorable and $(3,0,0)$-colorable. This is a relaxation of the Steinberg Conjecture that every planar graph without 4- and 5-cycles are properly 3-colorable (i.e., $(0,0,0)$-colorable).
A note on strong edge-colorings of 2-degenerate graphs
Rong Luo,Gexin Yu
Mathematics , 2012,
Abstract: We show that every 2-degenerate graph with maximum degree $\Delta$ has a strong edge-coloring with at most $8\Delta-4$ colors.
Linear Choosability of Sparse Graphs
Daniel W. Cranston,Gexin Yu
Mathematics , 2010,
Abstract: We study the linear list chromatic number, denoted $\lcl(G)$, of sparse graphs. The maximum average degree of a graph $G$, denoted $\mad(G)$, is the maximum of the average degrees of all subgraphs of $G$. It is clear that any graph $G$ with maximum degree $\Delta(G)$ satisfies $\lcl(G)\ge \ceil{\Delta(G)/2}+1$. In this paper, we prove the following results: (1) if $\mad(G)<12/5$ and $\Delta(G)\ge 3$, then $\lcl(G)=\ceil{\Delta(G)/2}+1$, and we give an infinite family of examples to show that this result is best possible; (2) if $\mad(G)<3$ and $\Delta(G)\ge 9$, then $\lcl(G)\le\ceil{\Delta(G)/2}+2$, and we give an infinite family of examples to show that the bound on $\mad(G)$ cannot be increased in general; (3) if $G$ is planar and has girth at least 5, then $\lcl(G)\le\ceil{\Delta(G)/2}+4$.
A New Lower Bound on the Density of Vertex Identifying Codes for the Infinite Hexagonal Grid
Daniel W. Cranston,Gexin Yu
Computer Science , 2010,
Abstract: Given a graph $G$, an identifying code $C \subseteq V(G)$ is a vertex set such that for any two distinct vertices $v_1,v_2\in V(G)$, the sets $N[v_1]\cap C$ and $N[v_2]\cap C$ are distinct and nonempty (here $N[v]$ denotes a vertex $v$ and its neighbors). We study the case when $G$ is the infinite hexagonal grid $H$. Cohen et.al. constructed two identifying codes for $H$ with density $3/7$ and proved that any identifying code for $H$ must have density at least $16/39\approx0.410256$. Both their upper and lower bounds were best known until now. Here we prove a lower bound of $12/29\approx0.413793$.
A relaxation of the Bordeaux Conjecture
Runrun Liu,Xiangwen Li,Gexin Yu
Mathematics , 2014,
Abstract: A $(c_1,c_2,...,c_k)$-coloring of $G$ is a mapping $\varphi:V(G)\mapsto\{1,2,...,k\}$ such that for every $i,1 \leq i \leq k$, $G[V_i]$ has maximum degree at most $c_i$, where $G[V_i]$ denotes the subgraph induced by the vertices colored $i$. Borodin and Raspaud conjecture that every planar graph without intersecting triangles and $5$-cycles is $3$-colorable. We prove in this paper that every planar graph without intersecting triangles and $5$-cycles is (2,0,0)-colorable.
Optimal open-locating-dominating sets in infinite triangular grids
Rex Kincaid,Allison Oldham,Gexin Yu
Mathematics , 2014,
Abstract: An open-locating-dominating set (OLD-set) is a subset of vertices of a graph such that every vertex in the graph has at least one neighbor in the set and no two vertices in the graph have the same set of neighbors in the set. This is an analogue to the well-studied identifying code in the literature. In this paper, we prove that the optimal density of the OLD-set for the infinite triangular grid is $4/13$.
Planar graphs without 5-cycles and intersecting triangles are $(1,1,0)$-colorable
Runrun Liu,Xiangwen Li,Gexin Yu
Mathematics , 2014,
Abstract: A $(c_1,c_2,...,c_k)$-coloring of $G$ is a mapping $\varphi:V(G)\mapsto\{1,2,...,k\}$ such that for every $i,1 \leq i \leq k$, $G[V_i]$ has maximum degree at most $c_i$, where $G[V_i]$ denotes the subgraph induced by the vertices colored $i$. Borodin and Raspaud conjecture that every planar graph without $5$-cycles and intersecting triangles is $(0,0,0)$-colorable. We prove in this paper that such graphs are $(1,1,0)$-colorable.
A relaxation of the strong Bordeaux Conjecture
Ziwen Huang,Xiangwen Li,Gexin Yu
Mathematics , 2015,
Abstract: Let $c_1, c_2, \cdots, c_k$ be $k$ non-negative integers. A graph $G$ is $(c_1, c_2, \cdots, c_k)$-colorable if the vertex set can be partitioned into $k$ sets $V_1,V_2, \ldots, V_k$, such that the subgraph $G[V_i]$, induced by $V_i$, has maximum degree at most $c_i$ for $i=1, 2, \ldots, k$. Let $\mathcal{F}$ denote the family of plane graphs with neither adjacent 3-cycles nor $5$-cycle. Borodin and Raspaud (2003) conjectured that each graph in $\mathcal{F}$ is $(0,0,0)$-colorable. In this paper, we prove that each graph in $\mathcal{F}$ is $(1, 1, 0)$-colorable, which improves the results by Xu (2009) and Liu-Li-Yu (2014+).
Page 1 /60989
Display every page Item


Home
Copyright © 2008-2017 Open Access Library. All rights reserved.