✦ LIBER ✦

On Parsimonious Edge-Colouring of Graphs with Maximum Degree Three

✍ Scribed by Fouquet, J.-L.; Vanherpe, J.-M.

Book ID: 120309419
Publisher: Springer Japan
Year: 2012
Tongue: English
Weight: 233 KB
Volume: 29
Category: Article
ISSN: 0911-0119
DOI: 10.1007/s00373-012-1145-3

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Acyclic edge coloring of graphs with max

Acyclic edge coloring of graphs with maximum degree 4

✍ Manu Basavaraju; L. Sunil Chandran 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB 👁 1 views

## Abstract An __acyclic__ edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The __acyclic chromatic index__ of a graph is the minimum number __k__ such that there is an acyclic edge coloring using __k__ colors and is denoted by __a__′(__G__). It was conj

Bipartite Subgraphs of Graphs with Maxim

Bipartite Subgraphs of Graphs with Maximum Degree Three

✍ Stanisław Bylka; Adam Idzik; Jan Komar 📂 Article 📅 1999 🏛 Springer Japan 🌐 English ⚖ 108 KB

Edge density and independence ratio in t

Edge density and independence ratio in triangle-free graphs with maximum degree three

✍ Jerrold Griggs; Owen Murphy 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 548 KB

A simple polynomial-time algorithm is presented which computes independent sets of guaranteed size in connected triangle-free noncubic graphs with maximum degree 3. Let nand m denote the number of vertices and edges, respectively, and let c '= m/n denote the edge density where c < 3/2. The algorithm

Edge-face coloring of plane graphs with

Edge-face coloring of plane graphs with maximum degree nine

✍ Jean-Sébastien Sereni; Matěj Stehlík 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 189 KB 👁 1 views

An edge-face coloring of a plane graph with edge set E and face set F is a coloring of the elements of E ∪F so that adjacent or incident elements receive different colors. Borodin [Discrete Math 128(1-3): [21][22][23][24][25][26][27][28][29][30][31][32][33] 1994] proved that every plane graph of max

On the size of edge-coloring critical gr

On the size of edge-coloring critical graphs with maximum degree 4

✍ Lianying Miao; Shiyou Pang 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 187 KB

The maximum number of edges in a graph w

The maximum number of edges in a graph with fixed edge-degree

✍ R.J. Faudree; J. Sheehan 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 633 KB

Suppose that n i> 2t + 2 (t/> 17). Let G be a graph with n vertices such that its complement is connected and, for all distinct non-adjacent vertices u and v, there are at least t common neighbours. Then we prove that and Furthermore, the results are sharp.