Canadian Mathematical Society
Canadian Mathematical Society
  location:  Publicationsjournals
Search results

Search: MSC category 05C15 ( Coloring of graphs and hypergraphs )

  Expand all        Collapse all Results 1 - 7 of 7

1. CMB Online first

Shaveisi, Farzad
Some Results on the Annihilating-Ideal Graphs
The annihilating-ideal graph of a commutative ring $R$, denoted by $\mathbb{AG}(R)$, is a graph whose vertex set consists of all non-zero annihilating ideals and two distinct vertices $I$ and $J$ are adjacent if and only if $IJ=(0)$. Here, we show that if $R$ is a reduced ring and the independence number of $\mathbb{AG}(R)$ is finite, then the edge chromatic number of $\mathbb{AG}(R)$ equals its maximum degree and this number equals $2^{|{\rm Min}(R)|-1}-1$; also, it is proved that the independence number of $\mathbb{AG}(R)$ equals $2^{|{\rm Min}(R)|-1}$, where ${\rm Min}(R)$ denotes the set of minimal prime ideals of $R$. Then we give some criteria for a graph to be isomorphic with an annihilating-ideal graph of a ring. For example, it is shown that every bipartite annihilating-ideal graph is a complete bipartite graph with at most two horns. Among other results, it is shown that a finite graph $\mathbb{AG}(R)$ is not Eulerian, and it is Hamiltonian if and only if $R$ contains no Gorenstain ring as its direct summand.

Keywords:annihilating-ideal graph, independence number, edge chromatic number, bipartite, cycle
Categories:05C15, 05C69, 13E05, 13E10

2. CMB 2016 (vol 59 pp. 440)

Zhang, Haihui
A Note on 3-choosability of Planar Graphs Related to Montanssier's Conjecture
A graph $G=(V,E)$ is $L$-colorable if for a given list assignment $L=\{L(v):v\in V(G)\}$, there exists a proper coloring $c$ of $G$ such that $c(v)\in L(v)$ for all $v\in V$. If $G$ is $L$-colorable for every list assignment $L$ with $|L(v)|\geq k$ for all $v\in V$, then $G$ is said to be $k$-choosable. Montassier (Inform. Process. Lett. 99 (2006) 68-71) conjectured that every planar graph without cycles of length 4, 5, 6, is 3-choosable. In this paper, we prove that every planar graph without 5-, 6- and 10-cycles, and without two triangles at distance less than 3 is 3-choosable.

Keywords:choosability, planar graph, cycle

3. CMB 2015 (vol 59 pp. 190)

Raeisi, Ghaffar; Zaghian, Ali
Ramsey Number of Wheels Versus Cycles and Trees
Let $G_1, G_2, \dots , G_t$ be arbitrary graphs. The Ramsey number $R(G_1, G_2, \dots, G_t)$ is the smallest positive integer $n$ such that if the edges of the complete graph $K_n$ are partitioned into $t$ disjoint color classes giving $t$ graphs $H_1,H_2,\dots,H_t$, then at least one $H_i$ has a subgraph isomorphic to $G_i$. In this paper, we provide the exact value of the $R(T_n,W_m)$ for odd $m$, $n\geq m-1$, where $T_n$ is either a caterpillar, a tree with diameter at most four or a tree with a vertex adjacent to at least $\lceil \frac{n}{2}\rceil-2$ leaves. Also, we determine $R(C_n,W_m)$ for even integers $n$ and $m$, $n\geq m+500$, which improves a result of Shi and confirms a conjecture of Surahmat et al. In addition, the multicolor Ramsey number of trees versus an odd wheel is discussed in this paper.

Keywords:Ramsey number, wheel, tree, cycle
Categories:05C15, 05C55, 05C65

4. CMB 2015 (vol 58 pp. 317)

Lewkowicz, Marek Kazimierz
Coloring Four-uniform Hypergraphs on Nine Vertices
Every 4-uniform hypergraph on 9 vertices with at most 25 edges has property B. This gives the answer $m_9(4)=26$ to a question raised in 1968 by Erdős.

Keywords:property B, coloring hypergraphs

5. CMB 2013 (vol 56 pp. 449)

Akbari, S.; Chavooshi, M.; Ghanbari, M.; Zare, S.
The $f$-Chromatic Index of a Graph Whose $f$-Core has Maximum Degree $2$
Let $G$ be a graph. The minimum number of colors needed to color the edges of $G$ is called the chromatic index of $G$ and is denoted by $\chi'(G)$. It is well-known that $\Delta(G) \leq \chi'(G) \leq \Delta(G)+1$, for any graph $G$, where $\Delta(G)$ denotes the maximum degree of $G$. A graph $G$ is said to be Class $1$ if $\chi'(G) = \Delta(G)$ and Class $2$ if $\chi'(G) = \Delta(G) + 1$. Also, $G_\Delta$ is the induced subgraph on all vertices of degree $\Delta(G)$. Let $f:V(G)\rightarrow \mathbb{N}$ be a function. An $f$-coloring of a graph $G$ is a coloring of the edges of $E(G)$ such that each color appears at each vertex $v\in V(G)$ at most $f (v)$ times. The minimum number of colors needed to $f$-color $G$ is called the $f$-chromatic index of $G$ and is denoted by $\chi'_{f}(G)$. It was shown that for every graph $G$, $\Delta_{f}(G)\le \chi'_{f}(G)\le \Delta_{f}(G)+1$, where $\Delta_{f}(G)=\max_{v\in V(G)} \big\lceil \frac{d_G(v)}{f(v)}\big\rceil$. A graph $G$ is said to be $f$-Class $1$ if $\chi'_{f}(G)=\Delta_{f}(G)$, and $f$-Class $2$, otherwise. Also, $G_{\Delta_f}$ is the induced subgraph of $G$ on $\{v\in V(G):\,\frac{d_G(v)}{f(v)}=\Delta_{f}(G)\}$. Hilton and Zhao showed that if $G_{\Delta}$ has maximum degree two and $G$ is Class $2$, then $G$ is critical, $G_{\Delta}$ is a disjoint union of cycles and $\delta(G)=\Delta(G)-1$, where $\delta(G)$ denotes the minimum degree of $G$, respectively. In this paper, we generalize this theorem to $f$-coloring of graphs. Also, we determine the $f$-chromatic index of a connected graph $G$ with $|G_{\Delta_f}|\le 4$.

Keywords:$f$-coloring, $f$-Core, $f$-Class $1$
Categories:05C15, 05C38

6. CMB 2009 (vol 52 pp. 451)

Pach, János; Tardos, Gábor; Tóth, Géza
Indecomposable Coverings
We prove that for every $k>1$, there exist $k$-fold coverings of the plane (i) with strips, (ii) with axis-parallel rectangles, and (iii) with homothets of any fixed concave quadrilateral, that cannot be decomposed into two coverings. We also construct for every $k>1$ a set of points $P$ and a family of disks $\cal D$ in the plane, each containing at least $k$ elements of $P$, such that, no matter how we color the points of $P$ with two colors, there exists a disk $D\in{\cal D}$ all of whose points are of the same color.

Categories:52C15, 05C15

7. CMB 2000 (vol 43 pp. 108)

Sanders, Daniel P.; Zhao, Yue
On the Entire Coloring Conjecture
The Four Color Theorem says that the faces (or vertices) of a plane graph may be colored with four colors. Vizing's Theorem says that the edges of a graph with maximum degree $\Delta$ may be colored with $\Delta+1$ colors. In 1972, Kronk and Mitchem conjectured that the vertices, edges, and faces of a plane graph may be simultaneously colored with $\Delta+4$ colors. In this article, we give a simple proof that the conjecture is true if $\Delta \geq 6$.

Categories:05C15, 05C10

© Canadian Mathematical Society, 2016 :