✦ LIBER ✦

On the number of colorings of a snark minus an edge

✍ Scribed by Richard C. Bradley

Publisher: John Wiley and Sons
Year: 2006
Tongue: English
Weight: 93 KB
Volume: 51
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20133

No coin nor oath required. For personal study only.

✦ Synopsis

For a given snark G and a given edge e of G, let (G; e) denote the nonnegative integer such that for a cubic graph conformal to G À feg, the number of Tait colorings with three given colors is 18 Á (G; e). If two snarks G 1 and G 2 are combined in certain well-known simple ways to form a snark G, there are some connections between (G 1 ; e 1 ), (G 2 ; e 2 ), and (G; e) for appropriate edges e 1 , e 2 , and e of G 1 , G 2 , and G. As a consequence, if j and k are each a nonnegative integer, then there exists a snark G with an edge e such that (G; e) ¼ 2 j Á 3 k .

📜 SIMILAR VOLUMES

On the Number of 3-Edge Colorings of Cub

On the Number of 3-Edge Colorings of Cubic Graphs

✍ Christian Szegedy 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 127 KB

In this paper we present a short algebraic proof for a generalization of a formula of R. Penrose, Some applications of negative dimensional tensors, in: Combinatorial Mathematics and its Applications Welsh (ed.), Academic Press, 1971, pp. 221-244 on the number of 3-edge colorings of a plane cubic gr

The number of edge colorings with no mon

The number of edge colorings with no monochromatic triangle

✍ Yuster, Raphael 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 639 KB

Let F(n, k) denote the maximum number of t w o edge colorings of a graph on n vertices that admit no monochromatic Kk. la complete graph on k vertices). The following results are proved: f ( n , 3) = 2Ln2/41 for all n 2 6. f ( n , k) = 2((k~2)/(2k-2)+o( 1))n'. In particular, the first result solves

On the number of list-colorings

✍ Quentin Donner 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB

## Abstract Given a __list of boxes L__ for a graph __G__ (each vertex is assigned a finite set of colors that we call a box), we denote by __f__(__G, L__) the number of L‐__colorings__ of __G__ (each vertex must be colored wiht a color of its box). In the case where all the boxes are identical and

On the two-edge-colorings of perfect gra

On the two-edge-colorings of perfect graphs

✍ Chính T. Hoàng 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 409 KB 👁 1 views

## Abstract We investigate the conjecture that a graph is perfect if it admits a two‐edge‐coloring such that two edges receive different colors if they are the nonincident edges of a __P__~4~ (chordless path with four vertices). Partial results on this conjecture are given in this paper. © 1995 Joh

The number of defective colorings of gra

The number of defective colorings of graphs on surfaces

✍ Tom Rackham 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 99 KB 👁 1 views

A (k, 1)-coloring of a graph is a vertex-coloring with k colors such that each vertex is permitted at most 1 neighbor of the same color. We show that every planar graph has at least c n distinct (4, 1)-colorings, where c is constant and ≈ 1.466 satisfies 3 = 2 +1. On the other hand for any >0, we gi

On the Vertex-Distinguishing Proper Edge

On the Vertex-Distinguishing Proper Edge-Colorings of Graphs

✍ Cristina Bazgan; Amel Harkat-Benhamdine; Hao Li; Mariusz Woźniak 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 189 KB

We prove the conjecture of Burris and Schelp: a coloring of the edges of a graph of order n such that a vertex is not incident with two edges of the same color and any two vertices are incident with different sets of colors is possible using at most n+1 colors. 1999 Academic Press ## 1. Introducti