Canadian Mathematical Society
Canadian Mathematical Society
  location:  Publicationsjournals
Search results

Search: All articles in the CMB digital archive with keyword chromatic number

  Expand all        Collapse all Results 1 - 2 of 2

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 2011 (vol 56 pp. 317)

Dorais, François G.
A Note on Conjectures of F. Galvin and R. Rado
In 1968, Galvin conjectured that an uncountable poset $P$ is the union of countably many chains if and only if this is true for every subposet $Q \subseteq P$ with size $\aleph_1$. In 1981, Rado formulated a similar conjecture that an uncountable interval graph $G$ is countably chromatic if and only if this is true for every induced subgraph $H \subseteq G$ with size $\aleph_1$. Todorčević has shown that Rado's Conjecture is consistent relative to the existence of a supercompact cardinal, while the consistency of Galvin's Conjecture remains open. In this paper, we survey and collect a variety of results related to these two conjectures. We also show that the extension of Rado's conjecture to the class of all chordal graphs is relatively consistent with the existence of a supercompact cardinal.

Keywords:Galvin conjecture, Rado conjecture, perfect graph, comparability graph, chordal graph, clique-cover number, chromatic number
Categories:03E05, 03E35, 03E55

© Canadian Mathematical Society, 2016 :