✦ LIBER ✦

Equitable edge-colorings of simple graphs

✍ Scribed by Xia Zhang; Guizhen Liu

Publisher: John Wiley and Sons
Year: 2010
Tongue: English
Weight: 199 KB
Volume: 66
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20499

No coin nor oath required. For personal study only.

✦ Synopsis

An edge-coloring of a graph G is equitable if, for each v ∈ V (G), the number of edges colored with any one color incident with v differs from the number of edges colored with any other color incident with v by at most one. A new sufficient condition for equitable edge-colorings of simple graphs is obtained. This result covers the previous results, which are due to Hilton and de Werra, verifies a conjecture made by Hilton recently, and substantially extends it to a more general class of graphs. ᭧ 2010 Wiley

📜 SIMILAR VOLUMES

Acyclic edge colorings of graphs

✍ Noga Alon; Benny Sudakov; Ayal Zaks 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 102 KB

## Abstract A proper coloring of the edges 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 __a′__(__G__), is the least number of colors in an acyclic edge coloring of __G__. For certain graphs __G__, __a′__(_

Vertex-distinguishing edge colorings of

Vertex-distinguishing edge colorings of graphs

✍ P. N. Balister; O. M. Riordan; R. H. Schelp 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 136 KB 👁 1 views

Circular colorings of edge-weighted grap

Circular colorings of edge-weighted graphs

✍ Bojan Mohar 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 99 KB

## Abstract The notion of (circular) colorings of edge‐weighted graphs is introduced. This notion generalizes the notion of (circular) colorings of graphs, the channel assignment problem, and several other optimization problems. For instance, its restriction to colorings of weighted complete graphs

Investigation on Interval Edge-Colorings

Investigation on Interval Edge-Colorings of Graphs

✍ A.S. Asratian; R.R. Kamalian 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 380 KB

An edge-coloring of a simple graph \(G\) with colors \(1,2, \ldots, t\) is called an interval \(t\)-coloring [3] if at least one edge of \(G\) is colored by color \(i, i=1, \ldots, t\) and the edges incident with each vertex \(x\) are colored by \(d_{G}(x)\) consecutive colors, where \(d_{G}(x)\) is

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

Edge colorings of complete graphs withou

Edge colorings of complete graphs without tricolored triangles

✍ András Gyárfás; Gábor Simony 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 59 KB

## Abstract We show some consequences of results of Gallai concerning edge colorings of complete graphs that contain no tricolored triangles. We prove two conjectures of Bialostocki and Voxman about the existence of special monochromatic spanning trees in such colorings. We also determine the size