✦ LIBER ✦

Edge-face chromatic number and edge chromatic number of simple plane graphs

✍ Scribed by Rong Luo; Cun-Quan Zhang

Publisher: John Wiley and Sons
Year: 2005
Tongue: English
Weight: 201 KB
Volume: 49
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20077

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Given a simple plane graph G, an edge‐face k‐coloring of G is a function ϕ : E(G) ∪ F(G) → {1,…,k} such that, for any two adjacent or incident elements a, b ∈ E(G) ∪ F(G), ϕ(a) ≠ ϕ(b). Let χ~e~(G), χ~ef~(G), and Δ(G) denote the edge chromatic number, the edge‐face chromatic number, and the maximum degree of G, respectively. In this paper, we prove that χ~ef~(G) = χ~e~(G) = Δ(G) for any 2‐connected simple plane graph G with Δ (G) ≥ 24. © 2005 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

Acyclic edge chromatic number of outerpl

Acyclic edge chromatic number of outerplanar graphs

✍ Jian-Feng Hou; Jian-Liang Wu; Gui-Zhen Liu; Bin Liu 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 176 KB

## Abstract A proper edge coloring of a graph __G__ is called acyclic if there is no 2‐colored cycle in __G__. The acyclic edge chromatic number of __G__, denoted by χ(__G__), is the least number of colors in an acyclic edge coloring of __G__. In this paper, we determine completely the acyclic edge

The independence number of an edge-chrom

The independence number of an edge-chromatic critical graph

✍ Douglas R. Woodall 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 77 KB 👁 1 views

A graph G with maximum degree and edge chromatic number (G)> is edge--critical if (G -e) = for every edge e of G. It is proved here that the vertex independence number of an edge--critical graph of order n is less than 3 5 n. For large , this improves on the best bound previously known, which was ro

The generalized acyclic edge chromatic n

The generalized acyclic edge chromatic number of random regular graphs

✍ Stefanie Gerke; Catherine Greenhill; Nicholas Wormald 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 224 KB 👁 1 views

## Abstract The __r__‐acyclic edge chromatic number of a graph is defined to be the minimum number of colors required to produce an edge coloring of the graph such that adjacent edges receive different colors and every cycle __C__ has at least min(|__C__|, __r__) colors. We show that (__r__ − 2)__d

Circular Chromatic Numbers and Fractiona

Circular Chromatic Numbers and Fractional Chromatic Numbers of Distance Graphs

✍ G.J. Chang; L. Huang; X. Zhu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 171 KB

This paper studies circular chromatic numbers and fractional chromatic numbers of distance graphs G(Z , D) for various distance sets D. In particular, we determine these numbers for those D sets of size two, for some special D sets of size three, for

Upper Bounds of Entire Chromatic Number

Upper Bounds of Entire Chromatic Number of Plane Graphs

✍ W. Weifan 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 35 KB

The entire chromatic number χ ve f (G) of a plane graph G is the least number of colors assigned to the vertices, edges and faces so that every two adjacent or incident pair of them receive different colors. conjectured that χ ve f (G) ≤ + 4 for every plane graph G. In this paper we prove the conj

The vertex-face total chromatic number o

The vertex-face total chromatic number of Halin graphs

✍ Lam, Peter C. B.; Zhang, Zhongfu 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 69 KB 👁 2 views

In this paper, we shall first prove that for a Halin graph G, 4 °xT (G) °6, where x T (G) is the vertex-face total chromatic number of G. Second, we shall establish a sufficient condition for a Halin graph to have a vertex-face total chromatic number of 6. Finally, we shall give a necessary and suff