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 - 3 of 3

1. CJM Online first

de Joannis de Verclos, Rémi; Kang, Ross J.; Pastor, Lucas
Colouring squares of claw-free graphs
Is there some absolute $\varepsilon > 0$ such that for any claw-free graph $G$, the chromatic number of the square of $G$ satisfies $\chi(G^2) \le (2-\varepsilon) \omega(G)^2$, where $\omega(G)$ is the clique number of $G$? Erdős and Nešetřil asked this question for the specific case of $G$ the line graph of a simple graph and this was answered in the affirmative by Molloy and Reed. We show that the answer to the more general question is also yes, and moreover that it essentially reduces to the original question of Erdős and Nešetřil.

Keywords:graph colouring, Erdős--Nešetřil conjecture, claw-free graphs
Categories:05C15, 05C35, 05C70

2. CJM 2009 (vol 62 pp. 355)

Král', Daniel; Máčajová, Edita; Pór, Attila; Sereni, Jean-Sébastien
Characterisation Results for Steiner Triple Systems and Their Application to Edge-Colourings of Cubic Graphs
It is known that a Steiner triple system is projective if and only if it does not contain the four-triple configuration $C_{14}$. We find three configurations such that a Steiner triple system is affine if and only if it does not contain one of these configurations. Similarly, we characterise Hall triple systems using two forbidden configurations. Our characterisations have several interesting corollaries in the area of edge-colourings of graphs. A cubic graph G is S-edge-colourable for a Steiner triple system S if its edges can be coloured with points of S in such a way that the points assigned to three edges sharing a vertex form a triple in S. Among others, we show that all cubic graphs are S-edge-colourable for every non-projective non-affine point-transitive Steiner triple system S.

Categories:05B07, 05C15

3. CJM 2002 (vol 54 pp. 757)

Larose, Benoit
Strongly Projective Graphs
We introduce the notion of strongly projective graph, and characterise these graphs in terms of their neighbourhood poset. We describe certain exponential graphs associated to complete graphs and odd cycles. We extend and generalise a result of Greenwell and Lov\'asz \cite{GreLov}: if a connected graph $G$ does not admit a homomorphism to $K$, where $K$ is an odd cycle or a complete graph on at least 3 vertices, then the graph $G \times K^s$ admits, up to automorphisms of $K$, exactly $s$ homomorphisms to $K$.

Categories:05C15, 06A99

© Canadian Mathematical Society, 2017 :