𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Circular chromatic index of graphs of maximum degree 3

✍ Scribed by Peyman Afshani; Mahsa Ghandehari; Mahya Ghandehari; Hamed Hatami; Ruzbeh Tusserkani; Xuding Zhu

Publisher
John Wiley and Sons
Year
2005
Tongue
English
Weight
122 KB
Volume
49
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

This paper proves that if G is a graph (parallel edges allowed) of maximum degree 3, then Ο‡β€²~c~(G) ≀ 11/3 provided that G does not contain H~1~ or H~2~ as a subgraph, where H~1~ and H~2~ are obtained by subdividing one edge of K (the graph with three parallel edges between two vertices) and K~4~, respectively. As Ο‡β€²~c~(H~1~) = χ′~c~(H~2~) = 4, our result implies that there is no graph G with 11/3 < χ′~c~(G) < 4. It also implies that if G is a 2‐edge connected cubic graph, then Ο‡β€²~c~(G) ≀ 11/3. Β© 2005 Wiley Periodicals, Inc. J Graph Theory 49: 325–335, 2005

πŸ“œ SIMILAR VOLUMES

Circular chromatic index of Cartesian pr
Circular chromatic index of Cartesian products of graphs
✍ Douglas B. West; Xuding Zhu πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 164 KB

## Abstract The __circular chromatic index__ of a graph __G__, written $\chi\_{c}'(G)$, is the minimum __r__ permitting a function $f : E(G)\rightarrow [0,r)$ such that $1 \le | f(e)-f(e')|\le r - 1$ whenever __e__ and $e'$ are incident. Let $G = H$ β–‘ $C\_{2m +1}$, where β–‘ denotes Cartesian product

Total chromatic number of planar graphs
Total chromatic number of planar graphs with maximum degree ten
✍ Weifan Wang πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 161 KB πŸ‘ 1 views

## Abstract In this article we prove that the total chromatic number of a planar graph with maximum degree 10 is 11. Β© 2006 Wiley Periodicals, Inc. J Graph Theory 54: 91–102, 2007

The size of edge chromatic critical grap
The size of edge chromatic critical graphs with maximum degree 6
✍ Rong Luo; Lianying Miao; Yue Zhao πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 216 KB πŸ‘ 1 views

## Abstract In 1968, Vizing [Uaspekhi Mat Nauk 23 (1968) 117–134; Russian Math Surveys 23 (1968), 125–142] conjectured that for any edge chromatic critical graph ${{G}} = ({{V}}, {{E}})$ with maximum degree $\Delta$, $|{{E}}| \geq {{{1}}\over {{2}}}\{(\Delta {{- 1}})|{{V}}| + {{3}}\}$. This conject

Maximum chromatic polynomials of 2-conne
Maximum chromatic polynomials of 2-connected graphs
✍ Ioan Tomescu πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 345 KB πŸ‘ 1 views

## Abstract In this paper we obtain chromatic polynomials __P(G__; Ξ») of 2‐connected graphs of order __n__ that are maximum for positive integer‐valued arguments Ξ» ≧ 3. The extremal graphs are cycles __C__~__n__~ and these graphs are unique for every Ξ» ≧ 3 and __n__ β‰  5. We also determine max{__P(

On the circular chromatic number of circ
On the circular chromatic number of circular partitionable graphs
✍ Arnaud PΓͺcher; Xuding Zhu πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 168 KB

## Abstract This article studies the circular chromatic number of a class of circular partitionable graphs. We prove that an infinite family of circular partitionable graphs __G__ has $\chi\_ c (G) = \chi(G)$. A consequence of this result is that we obtain an infinite family of graphs __G__ with th

Strong chromatic index of subset graphs
Strong chromatic index of subset graphs
✍ Quinn, Jennifer J.; Benjamin, Arthur T. πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 115 KB πŸ‘ 2 views

The strong chromatic index of a graph G, denoted sq(G), is the minimum number of parts needed to partition the edges of G into induced matchings. For 0 ≀ k ≀ l ≀ m, the subset graph S m (k, l) is a bipartite graph whose vertices are the kand l-subsets of an m element ground set where two vertices ar